"call $business_thats_part_of_a_national_chain in $town $state." That's a batting practice pitch right over the plate. The "in $town $state" tells it to use Google maps search. From there it should have no problem finding the business and phone number. Instead it tells me "here's what we found for $business in $town $state." Of course the first result is the business I'm looking for and I can find and call the number somewhere on the page but it's almost easier to just Google it directly.
The only time I'm willing to put up with this is when I'm driving and want to minimize interaction with the phone.
Maybe nobody uses them in public because it's faster, more precise and less obnoxious to type.
Looking up car parts would be nice ( "does $chain_store in $town have $partnum" and "$other_chain_stire in $next_town_over have $partnum") is hilariously easy from a implementation perspective since everything but slapping the voice recognition on top and mapping key words to software commands has been solved for a long time. (e.g. http://showmetheparts.com/).