The New (11/08) Google app works like magic! I have been using the "voice search" funtionality of the new google app for a day now, it has returned useful results 80% of the time, mainly failing on vanity searches. The location aware voice search is amazing, speak "pizza", "McDonald's", "library", etc into the phone and the google app returns a list of locations near you - complete with one touch phone dialing and one touch directions leveraging the map.app.
With this new functionality I have moved the google.app from screen 2 to the home screen, and the whiz bang functionality of this application has moved it up to my number one demo app when showing non iPhone users what the iPhone can do.
Dissappointment, of course, I have not been able to get the voice search to work on my address book, in theory the google app should be able to function as a "one touch" voice dialer, but with my current configuration, it does not seem to search through my contacts when using voice search. Maybe the next version will inprove contact search!
Highly Recommended.. price: FREE