When I worked at Google, I think many of us were surprised by how often people outside the company would talk about Microsoft as a competitor. Inside the company though, we rarely talked about Microsoft. In fact, the use of the word Microsoft came up far more often in the context of "so-and-so used to work for Microsoft, ask him how to do x,y,z." The ex-Microsoft engineers at Google were generally revered as world-class talent, and plenty of laptops ran Windows. Of course there were also many Macintosh laptops, and some laptops running Linux, but for the most part nobody was ever consumed with the idea of Microsoft-as-enemy. It was pretty much a given that the media was far more concerned with the perceived battle between the big boys on the block than were the employees.
At Google the conversations about competitors nearly always focused on "who owned search in which country". There are places around the world where Google is not #1 in search, and consistent with the Ten things Google has found to be true, it's best to do one thing really, really well, and Google's one thing is search. Google focuses on search, and anybody, anywhere, who is trying to do search better than Google is a competitor. So yes, Bing from Microsoft is a competitor, but so are Baidu (China) and Yandex (Russia).
And search is far from done, both in quality and availability. The search quality efforts are continuing, and the availability represents Google's long-tail. Can they get more people performing more searches more frequently? That's a function of the number of countries and languages (and sometimes politics), devices and connectivity, and the ease of which Google can accept and process payments from advertisers. Not everybody who wants to advertise on Google in the world has a credit card yet.
It may be the case that better tools for advertisers and unlocking behavioral differences in ad spending and saturation by geographies may yield greater revenue opportunities than the other Google products that the media perceive as competitors to Microsoft. At the end of the day, Google has a search empire to grow and protect, and threats to owning search in any geography, or controlling access to said search, or tools that enable advertisers to spend more easily with other products are the real competitors.