I downloaded the free Google voice search application for the IPhone this evening. Spent some time experimenting. Its voice recognition is good, but has some of the typical failings of such systems, missing some of the interpretations. I like the way it is designed so that whenever you put the phone up to your ear it goes into voice mode, once I understood that it was very convenient. Screen rotation is automatically turned off, but if you turn it on you no longer get the phone-to-ear voice search activation.
It asks to use your location ( I do not have GPS ) and says it will use that data, but it showed me no local restaurants when I searched for them. Would also be nice if gave access to data like my contact list, but it does not. The mobile app also allows you access to what seems like most of the other Google applications as well, which is convenient. Overall good, a bit easier than using the keyboard which I still have some trouble with, providing it understands your voice. Have not tried in a noisy environment yet. To my knowledge only available now for the IPhone. Worth trying for the price.
Update: Later I was able to get the local search to work, since I have no GPS, it uses proximity to my 5-digit zip, which is correct. When it did or did not show local search seemed a bit haphazard .. I also discovered that there are some words that the app will just not interpret, even after many tries, undermining its convenience. A mobile link to the Google (Beta) cloud. Plus more about their speech recognition method.