Dave.
I picked up an old Orange M500 from eBay and got it unlocked, it works great on O2. Phone + unlock was less than £35. I got a 2nd hand Bluetooth GPS Ariel and I have TOMTOM 6 on it now.
A company called HTC makes loads of PDA's then rebrands them to Orange "M" series, O2 "XDA's" ect. So they are all pretty much the same. There is a web site that the name escapes me, but it gives details on how to unlock them, and there are loads of free software for them.
But IMO the old m500 does what I need, plus is a cheap Sat Nav. PM if you interested and I’ll dig out the web address.
I must admit those XDA orbits with the built in GPS are very good, but I will wait until they are a bit older and pick one up on the cheap.
Good luck, Ian