I have a Palm Vx with the Navman add on for GPS. It has its own internal chargable cell which seems to hold its charge very nicely. The software for Geocaching is rather good (GeoNiche i've found is one of the best) and it has a Quad Helix antenna. Under trees the signal degrades slightly, occasionally loosing the 3d fix (altitude) but still gives you the 2d lat/long fix to within a couple of feet accuracy.
Having said that if you plan to survive anywhere without electricity to recharge such a unit for some time, you're in trouble when it runs out of charge as it only has the internal chargable cell but that makes a change from such addons using the PDA's internal battery to power the GPS module.