Good question. I am a Russian speaker - ran the same searches on google.ru and got much better results (than google.se). Were Google.ru's results better than Yandex? Probably not.

Perhaps the problem isn't quite as fundamental (non-English NLP sucks) but has more to do with secondary Locale handling in specific countries?

Interesting observation on US-centricity (is that a word?) nonetheless. Many major US Corps derive > 50% rev from outside of US. Not sure if GOOG is one of those.