Google has an interesting-looking Voice Search Demo online. The way it says it works is that you call the number, say your query then go to a link that will have your search results.
As far as I can tell, the current demo doesn't address the issue of how a system that supported multiple simultaneous users would match users with output (caller ID? cookies? dedicated dialup?) but it seems like Google is thinking ahead to the needs of cell phone surfers….