any nokia with built in GPS and symbian is now sporting free voice guided navigation; I have only tried it on the Nokia 5800 in London using Thai language for directions.. works beautifly (though battery life is very short with screen constantly on and GPS constantly aquiring signal).
I used nokia maps loader so that I had the maps in the memory of the phone before calculating journeys etc. I had a choise of a huge number of maps available (good coverage for most of asia, europe and north & south america), and an extensive choise of languages for voice guildance.
Well Nokia maps loader doesn't work for me and my N900... And i was talking about the map of BG which is outdated probably arround 2-3 years. In a word if i ever need such an app i think i will buy smth like tomtom or whatever supports maemo...