The problem is that natural languages are at least context-free, and no algorithm exists (can exist?) to parse context-free languages in less than polynomial time, with respect to the length of the sentence. You can approximate by parsing with probabilistic finite-state machines, but they get led down blind alleys and can't backtrack, so they're inaccurate. Let me know if you'd like me to elaborate on this with examples (or you can Wiki "garden path sentence" and probably imagine the problem).
I'm also sure they're not doing supervised word sense disambiguation. That's in a poor state too, and imho isn't even a good idea. The whole concept of having someone list out the "senses" of a word is misguided, because it's totally unclear how fine-grained you should be. And then you need at least a couple of hundred labelled examples for every word...
Most of the examples they give are best explained by dimensionality reduction techniques, which have been popular in information retrieval for some time. Google have undoubtedly invented some secret sauce, but they've also just got orders of magnitude more data and processing power.
But yeah, context sensitive stuff can be way worse.
Unless new evidence has surfaced in the years since I finished a degree in linguistics, there's only a couple of pieces of evidence for language constructions in natural languages that can't be generated by a context free grammar, like a Adv1Adv2Adv3Adj1Adj2Adj3 construction in Zürich dialectical German (where Adv = adverb and Adj=adjective, and numbers represent which adverb modifies which adjective).
I do have a long history of over-analysing simple mathematical games, though.
I have a more specific question about Google Search that I'd like to see answered. To what extent do they model specific languages, versus training classifiers? Are they really grokking sentences or sentence fragments, or do they have enough training data to fake it, like Bill Gates in "Petals Around the Rose" [1]?
[0] http://googleblog.blogspot.com/2010/01/helping-computers-und...
[1] http://www.borrett.id.au/computing/petals-bg.htm