We're using a HTC Touch Cruise for full paperless (Tom Tom, Memory Map and Geoscout 2). Can be away for weeks and keep totally up to date.
However, the GPS on most phones (including the Touch Cruise) do not use the SiRF Star III GPSr chipset, and it means the GPS is no where near as accurate as you might expect. You need to be moving at a reasonable pace for it to make any sene of location, and it just stops working inder tree cover.
Hence they work fine for Sat Nav, or Memory Map, but no where near as good as a SiRF Star III GPSr for homing in on a cache.
So, we use a £75 eTrex H for the final search, and more often than not it will put us within spitting distance, even under heavy tree cover.
You can get there with the phone, and we have done a couple that way, but it is a much more painful experience.
If you enter "sid and bob pda update" into google and hit the fisrt link, you'll find a site which will prove some good feedback on one Geocacher's experiences of PDA and how they use it.