An interesting article in Pandia about an overlooked area of search - Searching Google for words with accents. The bottom line is that it's difficult and fiddly to do it, and it depends on a number of different factors that the searcher cannot control. Let's take the example (as given) by Pandia for Mexico and MÃ©xico. A search will probably return sites that contain either word, but to force the engine to return hits with the accented version a search for +MÃ©xico will pretty much work (though there may be a few oddities caused by inbound links.
However, results will differ depending on IP address, language of the Google home page being used, and preferred language. Now, this is useful as far as the searcher is concerned, since it should result in rather more accurate results, but it's going to be a concern for search engine marketers, since it makes the idea of being (say) #8 in Google a rather moveable feast, - is it #8 for Google.com users, or for Spanish language users? Still, no-one said that internet searching was supposed to be easy, did they?
Of course, it doesn't help either when we start to look into the results in a little more detail. Searching on Google.co.uk (searching the web, not just the UK) a search for Mexico returns 671,000,000 results, as does mexico (with a lower case). However, searching for MÃ©xico gives me 665,000,000 results, but a search for mÃ©xico 6,000,000 less, with 659,000,000. When we get into the insanity of searching for mÃ©xico -mexico with a result of 725,000,000 things certainly get a little more confused again. My one crumb of comfort is that searches on Ask.com tend to be rather more stable, but even then, not perfect. All goes to show - don't trust search engine results!