I have a Ipaq 5550, which has the bluetooth, so I can even use it with my bluetooth GPS and not take my etrex out of my pocket. I also have GPX sonar installed (recently) and an ebook reader, and use memory map to provide me with the OS maps. I consider this to be a true paperless solution. I have had to buty a couple of memory cards, but these are very cheap at the mo ( £30 for a 512). I have tom tom navigator which I use as I drive (which I do as a living) so if a cache appears by the side of the road I can stop and do it. Then I have a little app called ROT13 decode, which decodes the clues quickly rather than by hand if I am using papaer sheets as I sometimes do.
The 5550 is a fairly expensive Ipaq, and is not really required as a slightly cheaper model would do. At the end of the day the choice is yours, but I personally would try and avoid palm powered devices as the software tends to be a little less available.
I have just seen a PPC called the mitac mio 168 which comes with an integrated GPS, but I have no idea how good this one is. Pocketgpsworld have recently done a review of this one which retails at about £220 so this seems like a real bargain on the face of it.