Tellme Beta

Supposedly the best app in the mobile search category, they were acquired by MS and only support a few phones by Cingular/ATT and Sprint:

http://beta.tellme.com/content/tellme_by_mobile_overview.php