On one of those rare occasions, Google is actually playing catch up with MS’s Bing (which I actually prefer and use as my primary search engine and map app). Google Maps now as Voice Search in their v4.1 for Windows Mobile.
To search by voice, simply press the call hardware button, which will pull up a search prompt, then say the name of the business. It can detect different variations of English (American, British, Indian, Australian, & New Zealand English) and also Mandarin.
You can download the cab here or m.google.com/maps from your mobile web browser to download directly to your phone.