Link:
http://www.telegraph.co.uk/scienceandtechnology/technology/apple/3479305/Google-iPhone-voice-recognition-tool-baffled-by-British-accents.html

Some examples:
"When asked to search for "iPhone" the results varied wildly. A user with a Scottish accent found his phone opted to search for the term "sex" instead, and suggested a link to an adult web site. On a second attempt, the search engine looked for "sledding".

Asked in a Kentish accent to search for "iPhone", it came up with "my sister" and "Einstein", while a Surrey user was offered "myspace" as well as "Einstein"."

I can see the problem with most accents (Scottish and Surry, I would expect it to have problems with) but Kent?

800-goog-411 is a voice search of business phone directories available from google. It does not require a special phone or an internet connection.
It has been speculated that these interactions are used to train and test google's voice recognition. I do not know if it uses previous history specific to the caller's phone number.

It used to first ask for the desired city and state.
After finding that it would then ask for your query, a business name or category.

More recently it asks for both the location and query together.
It has been my experience with this method that it most often either gets them wrong or realizes it does not understand. It may then ask for the location separately.

A very interesting detail and I believe that there are connections between these services.