Google's S60 'portal' search utility, 'Google Mobile App' just got itself an update to v2.03(8), bringing voice searching - and it works rather impressively. Bring up the S60 3rd Edition utility in the usual way (e.g. by pressing 'C' on the homescreen) and then press and hold the green call key to speak your search string. Some screenshots, videos and links below.
You can get Google Mobile App for yourself by going to m.google.com in Web on your phone - the version for S60 5th Edition (with no 'C' key, among other aspects) comes up as 'Not compatible' but you can persevere as long as you're happy to get to the utility another way.
Once a search match is found, you're shown any results, optionally sorted by distance from your current location, in the usual way.
Google India has done a demonstration video, embedded here. Of note is the complexity of phrases which can be used and also the multi-language abilities - apparently Mandarin (Chinese) is now supported. Comments welcome if you've got the time to try this out fully!
From Google's announcement, on the subject of Mandarin support:
Up until now voice search has only been available in English, but the new version of Google Mobile App for Nokia S60 devices works for Mandarin speakers, too. We're really proud of the work we've done with Mandarin speech recognition, both because it's the most spoken language in the world, and because of the engineering challenge. To get Mandarin speech recognition to work, we had to learn a lot about this fascinating language — the differences between traditional and simplified Chinese, its tonal characteristics, automatic segmentation of text into words, pinyin representations of Chinese characters, sandhi rules, the different accents and languages in China, unicode representations of Chinese character sets...the list goes on and on.
Mandarin speakers can now search by voice for complex queries like 清华大学附近的水煮鱼 (which translates to "water-boiled fish near Tsinghua University"). Although this only works on the Nokia S60 at the moment, we're working on adding support for Mandarin speech recognition to our products on other mobile platforms, such as Android and iPhone. And bear in mind that this is a first version of our system in Mandarin, and it might not be as polished as our English version. For example, if you have a strong southern Chinese accent, it might not work as well as for people with a Beijing accent. However, our system will improve over time, so please give it a try!
(hat tip to Clinton Jeff for the YouTube link for the second video clip)