My current solution to creating tracks is to use 2 gps, mainly I use a HTC Wizard (TMobile MDA2 / O2 XDA something) with a Holox BT-321 bluetooth GPS module. In addition I've been carrying a GlobalSat DataLogger DG100 borrowed from work.
Pocket PC
The PocketPC come Phone runs Windows Mobile 5 and I use NoniPlot for creating tracks. I've tried several other apps, but nothing free has been as good at recording the tracks. I plan on writting an application aimed for OSM mappers, I've not written the spec yet, but I want it to be easy to use for tagging on the fly. The Holox gps was very cheap buy from ebay, and I'm very impressed. It aquires position very quickly and battery life is incredible, I think I've ever only charged it up 3 or 4 times, it has a Lithium Ion battery which matchs the one supplies with some nokia phones, so if the battery ever did fail replacements should be easy to find.