I agree that it's possible, but I think the last point in your argument actually makes Google harder to displace than easier.

If someone came out with a better web search engine than Google right now, I probably wouldn't switch. This is because Google search is so integrated with other services that they understand intent way better, and you can perform searches with far less input that you would have to give otherwise.

For example, doing a search for "my flights" or similar does not only search the web, but also my gmail account, matches upcoming flights with data, and returns what is relevant to me. Similar arguments can be made based on phone data (locations, activity) and integration with products like Maps, Calendar etc. Google Now and On Tap are great examples of features and functions that cannot be trivially replaced by a better search algorithm.