I was having this very discussion in a Vodaphone shop - she told me that things such as Blackberry and iPhones could only use GPS if they did it via the mobile service which meant having a contract which I specifically did not want.
Looks like an iPaq is the answer to my problem as well - and can you just put your Pay-as-you-talk sim card straight into it to continue using your phone without problems?