The new version of the Google Mobile app for the iPhone has just been released with the ability to speak your search. The application also takes your currently location into consideration when doing a search.
In my testing this application works very well and quickly over EDGE on an iPhone 2G. Two little niggles that I have with it are that it doesn’t search the address book by voice and that when I searched for "Chinese" I had to click on "Local" before it showed me the restaurants in my area.
Source: Google Mobile App page.
Download: iTunes App Store link.