My first attempt is inspired by Peter Norvig's spelling corrector using a corpus built from the places2k.txt file, but it gets confused when the words are transposed. My guess is that Google is using some sort of n-gram based approach for maps and search, where as their little sidebar map is similar to what I built. (Or only applied to the most clear-cut n-gram—a little while ago there was a search for the movie "The end of the world" that would return a definitive date, which went slightly viral.)
Try searching in Google for "San Francisco" versus "Francisco San." Maps is fine, the search is fine, but only the first version brings up the little related info sidebar on the search page.
I'm surprised that Apple had such a hard time dealing with search, since they have some experience with Siri. I should have trusted this guy's opinion more:
On the other hand, that's not a mistake you can make, because "San Francisco" in the minds of people really is "Sanfrancisco", a single word. Why would anybody spell "San Francisco" as "Francisco San"? In fact Google should differentiate heavily between these 2 terms, as they aren't similar at all.
Google also does a lot of other neat things, like translations for city names. Searching on google.com for "Bucuresti" (my town) brings up the sidebar for "Bucharest".
And on GMaps, I'm never afraid of using "str", "strada", "soseaua", "sos" which are different Romanian words and abbreviations for "street". The results aren't the same in these cases (nor they should be actually) but because Google also searches within the addresses of businesses it's usually able to give me an accurate answer to what I mean.
It gets more complicated when you realize "oh, yeah I need to add 'NE' because it's in the Northeast part of the city". So now it's "Portland 4485 Belmont NE". If you were to think about it before you started typing, it'd be "4485 NE Belmont Portland" but correcting on a phone is so painful that you want to just keep typing.
I'm using a Galaxy Nexus and have been very happy with the standard Maps app. Last weekend the family was walking on trails and it got us back to the trailhead using walking directions. Neat. I've been less than thrilled with how poorly the phone seems to do with finding and keeping a GPS signal, particularly in a car on the freeway in areas I don't know.
That is on top of the issue of searching for something like "1st and University", which takes me to some L'ecole in Paris, France rather than the intersection that is a block from me. It's as if they don't factor in your current location at all. I know on the desktop I frequently look at maps of faraway places, but I'd suspect that people tend to look for things near them while on mobile devices.