I wouldn't say palm is out of the question. Stryke, the visor isn't a palm creation, it's a handspring creation, you can't just compare them because they run the same OS. AFAIK, the palm Vx is pretty damn robust. Visors must be pretty crappy to die when they're dropped, as my e740 is a lot heavier and I've dropped the damn thing on the floor from waist height at least twice by accident, not even a scratch.
The Vx is out of production, so good luck trying to find it with a warranty. On ebay UK, the average going price for a Vx is £40-60, and the keyboard £20 or so. Most are said to work, so if they arrive and don't then the seller is liable.
I wouldn't really recommend any palm models after the Vx, but that's just my opinion.
As for laptops, expect to be paying out of every orifice for one that's around A4 sized with a good battery life. The IBM Thinkpad t39 gets good reviews, and it's pretty robust. Stay away from sony, dell, etc., they break when you look at them. Toshibas are excellent for robustness, but I can't offhand think of any they've made that would fit your criteria.