I used Nav4ALL on my K800i. I was a big Fan, but there were a few little things to note.
Maps are downloaded as needed and not stored for future. = Data usage (but not much admittedly)
Routes are downloaded as needed, so if you taka wrong turn, it has to dial up to get a new route, OK so long as you have a signal. (again, not huge data usage)
Navigation is arrows on a white background, no live maps, last version I used anyway.
It also likes to take you off every slip road on the Motorway (UK), round the roundabout and back on! Trying to judge when it was ACTUALLY the right turn off is a great game to play! :P
But for Free, it was OK, not bad at all.
By comparrison, £45 for 3 year subscription to your built in fully fuctional
N95 GPS system is a bit easier. And probably almost what it would cost to buy an external Sat receiver for N4A anyway?