Google became very popular very quickly because it gave much better results much faster. The more that Google allows quality to decline, the faster they approach a non-recoverable tipping point. Just ask Yahoo how quickly that can happen. Google may seem entrenched, but they have a shaky hold on search that is only as strong as its result quality. They are entrenched in
advertising, but only because that's where searchers go to search.
Users may be entrenched in other Google products-- Gmail, gcal, docs, etc-- but not search. Someone using all those other Google products could change their default search engine and have zero impact on the rest of their digital life.
I'm shopping around for a preferred alternative right now, I just haven't settled yet.