Howdy, I have a Nokia 6110 navigator and I use the GPS which comes with the phone. I have not had any problems caching with it. I am pretty sure the datum used is wgs84 (i can not find anywhere to change the datum) The co-ordinate format that this phone uses is decimal degrees so make sure you convert from what ever format (usually deg min sec) the cache is in.
Cheers
yeti