The latest version of Windows Live Search for Mobile adds speech recognition - so if you're somewhere you can't type your search, all you need to do is speak it. I've been trying it out on some of the harder items to recognise, especially words with sibilants - and was impressed that it handled both "Cinema" and "Sushi" first time.
Of course map search is a relatively closed domain, so the range of terms that are going to be used is small (and most queries are going to be single words or short phrases). That means that it's going to be easier to build an effective recogniser, but even so, this is running on a low powered mobile device. It's not even one of this year's phones...
Well worth a try if you're using Windows Mobile 5 or 6.
[Update: Speech recognition is done on the server, not the device. That makes more sense - all the device needs to do is encode the speech and send it back to the server - a much lower power job. The servers can be as powerful as you like...]