Right after Microsoft acquired TellMe, Google Labs has launched a local search using voice recognition at 1-800-GOOG-411.
In my tests, Google Voice Local Search worked fairly well, good enough that I intend to use it for most local searches from my cell phone. Others report more mixed results.
Some of the reaction to to this has been interesting. Paul Kedrosky says, "Google just killed the directory assistance business," a statement that probably gives too much credit to Google, but may accurately describe the long-term trend.
Tim O'Reilly mentions Googler Peter Norvig's love for big data and wonders if this is "designed to harvest voice data to build Google's own speech database" to create a "competitive advantage in speech recognition."
Probably true, but I doubt that is their primary motivation. Rather, I suspect they are trying to work around the UI problems of search on mobile devices.
I am convinced that the long-term success of mobile search will require overcoming the issue of the tiny screens on cell phones and other mobile devices.
While there are a few promising paths to manage with the small screens -- including Patrick Baudisch's clever UI work at Microsoft Research, search personalization to display only the most relevant data in the limited space available, or the iPhone's use of the entire surface of the device as a screen -- I am concerned that these approaches may rapidly hit their limits.
Rather, I suspect we will have to replace the tiny screen with something else. One good option is a voice recognition interface like Google Voice Search or the one TellMe has developed. These make the tiny displays unnecessary.
Another approach may be to make the tiny screen a huge screen. The most promising work I have seen here is the Virtual Retinal Display being developed at the HIT Lab at University of Washington. By drawing video images directly on your retina, it replaces tiny displays with a massive one that covers your full field of view.
The constrained input and display on mobile devices cripple the potential of mobile search. Resolving these issues within the form factor of these devices is not trivial. A voice interface, like Google Voice Local Search, may be one of the better solutions.