Out of the two, I prefer the X31 in spite of it being slightly larger/heavier. I bought both models at one point - a brand new X40 and a used (but nearly mint) X31, and the X31 was the one I kept. I found the hard disk in the X40 to be too slow, and due to the type of disks the chassis can accomodate it could be difficult to fit a faster disk. Even though the X31 is larger than the X40, it's by no means bulky or heavy.
The keyboard on the X31 is fantastic - easily the best laptop keyboard I've ever used and probably the best non-mechanical keyboard I've used, period. I got mine from eBay and bought a new battery for it, on which it would run for somelike like 5 or 6 hours (sorry, can't remember, my ex has this laptop now).
I can't speak for Linux support, I stuck with Windows XP and it was nice and snappy. I wouldn't have thought it would be too difficult to get running under any modern variant of Linux, although you might want to check into the wireless/Bluetooth card. There are several possible Wifi/BT cards fitted to these machines IIRC.
Just watch out for marks on the screen from the pointing stick, and wear to the rubberised lid. The rubberised case gets marked quite easily, so if these things bother you, you might want to ask the seller. Ex-corporate laptops also tend to have stickers on the lids and when these get removed the rubber is often damaged. I was fortunate to get a machine that was very well looked after and only had a little bit of wear on the corner edges where it had been slipped in and out of its bag.
I spent a long time finding a good X31 - in my experience the privately owned ones tend to be in better condition.