Because Google usually doesn't use its patents aggressively. They will use them defensively, though, or even as a counter-attack. That's why I think it's incredibly stupid of Microsoft to be attacking Google with search patents through Rockstar. If they piss off Google enough to start using their search engine patent trove against Bing, it may be game over for Bing. Microsoft should already consider itself very lucky that Google isn't as spiteful and vengeful as Apple, or Google would've used them since day one of them going after Android OEMs.

That being said, I think the only solution to beating Google is developing something disruptive, and I mean that in a very classical and traditional sense (not the way disruptive is used to mean anything these days). It means you have to build a type of a search engine (or search solution) that Google not only has no interest in pursuing (due to conflicts of interest/opposite business incentives), but probably can't pursue, or not without employing dramatic shifts in how they do search (which again, makes it even less likely for Google to pursue and try to beat this new "disruptor").

And no, don't look at Bing to provide that. They're a "direct competitor" to Google, and they will always be, because they want to be "in the exact same business" Google is, and therefore, I don't think they'll ever radically change the way they build a search engine compared to Google.

So what can such a disruptive solution be? I can't say for sure, because it probably needs more factors/benefits on its side than just one, against Google. Social "may" be a way to disrupt Google, although I think Google is already rapidly adapting to this attack vector.

I think another could be "extreme-privacy", which Google wouldn't pursue anytime soon without really rethinking how its search business works.

Disruption also means attacking incumbent companies with much fewer resources through innovative business models and cost structures. Do something that would make Google's billions of investment in infrastructure irrelevant. A P2P search engine like YaCy or Faroo seems to be part of that solution. Perhaps what can/will kill Google is a crowdsourced super-search engine, that ends up surpassing even Google in most capabilities, because Google would be just one company, fighting against the whole resources of the world.

As in classic disruption, you also have to consider this new type of search engine will be much poorer than Google in some competition factors (at least initially). I think that is the "relevance" factor. As the op mentions, it's going to be very hard for anyone or anything to beat Google in relevance. They have too much of a headstart. But perhaps there will be such a thing as "good enough" in search, too. Maybe we're not there yet, but perhaps we will be in 5 years, or 10 years. Until a few years ago we kept wanting faster and faster Intel processors. Now we think mobile ARM processors are more than good enough for most of our daily activities.

A crowdsourced P2P search engine powered by billions of people could perhaps reach that point, too, while offering some of that "extreme privacy" and other benefits that Google can't offer.

Still, how do you get that first "10 percent" of users, that end up changing the paradigm, to start using a service that's much less relevant than Google today? You do it in the same way other disruptive technologies win out against incumbents. You promote the other benefits, that Google can't and won't match - benefits that will be important to those "first 10 percent", until you reach critical mass, and then you should be fast approaching that "good enough" relevance, too, and get even more users after that.