Paul Graham put it best in his Frighteningly Ambitious Startup Ideas article.
The point when it became clear to me that Microsoft had lost their way was when they decided to get into the search business. That was not a natural move for Microsoft. They did it because they were afraid of Google, and Google was in the search business. But this meant (a) Google was now setting Microsoft's agenda, and (b) Microsoft's agenda consisted of stuff they weren't good at.
Microsoft : Google :: Google : Facebook.
That does not by itself mean there's room for a new search engine, but lately when using Google search I've found myself nostalgic for the old days, when Google was true to its own slightly aspy self. Google used to give me a page of the right answers, fast, with no clutter. Now the results seem inspired by the Scientologist principle that what's true is what's true for you. And the pages don't have the clean, sparse feel they used to. Google search results used to look like the output of a Unix utility. Now if I accidentally put the cursor in the wrong place, anything might happen.
The way to win here is to build the search engine all the hackers use. A search engine whose users consisted of the top 10,000 hackers and no one else would be in a very powerful position despite its small size, just as Google was when it was that search engine. And for the first time in over a decade the idea of switching seems thinkable to me.
Bing will improve over time, and maybe at some point they'll come close to rivaling the quality in search results that we can see from Google. Google have done well to fight off SEO spam, but I think people overall are happy with the quality of Google's search results. As Paul Graham suggests, search could be "won" by someone that can increase quality as well as keep it simple, in the same way that Google did from the beginning.
Bing won't do this, and as such will never dominate. Even if the quality of searches were the same people would probably still choose Google. The closest to doing this is DuckDuckGo.