I think the difference in quality between Google and Bing search results is negligible; at this point it's just a matter of mindshare as to whether people, on average, go to www.google.com or to www.bing.com when they want to look something up. There's no vendor lock-in propping up Google, to the extent that there is behind the Windows or iTunes monopolies. Mindshare can be altered, Microsoft just needs to figure out how to do it.
In technology, it is rare that a leader loses it's place in the market. More often, a new technology is pioneered by a new company that makes the old technology less relevant.
IBM never lost the mainframe market, but did not dominate the PC market. Google did not take over PCs, but dominates search. There are many more examples like this.
There was also a company called Novell that pretty much invented the business of networking PC's, but where are they now?
Google supplanted Altavista largely because they made huge strides in a rather new field. While it's definitely possible, it's a little hard to image someone coming along with a web search that's impressive enough to supplant Google. It's more likely that "search" would evolve into something not entirely comparable to today's search, and replace them.