1-800-goog-411 (http://www.google.com/goog411/)

Basically a 411 service with automatic speech recognition. Not necessarily a web search, but they are far along this track.