You just need millions of computers, millions of petabytes of net traffic and a lot of time to have the same index as Google. Easy.
For example, look at how useless Bing is. And that's Microsoft!
Prediction: some near-future Snowden document release will catapult DuckDuckGo or some other privacy-oriented search alternative into the limelight in a hockeystick curve growth kind of way. Maybe something that proves the NSA is firehose sharing de-anonymised Google/Bing search data with HealthCare Companies or the Insurance Industry or the IRS, and that there's widespread punitive action going on based on simplistic or poorly thought out responses to people's search history (people being denied health insurance because they did a few too many Google searches when their mother was diagnosed with cancer, or car insurance rates being raised across the board for people who search wine labels online...) All of a sudden someone who's "good enough" at search, but has TOR hidden service endpoints and nothing associated with them that comes under Five Eyes legal jurisdictions is going to look worthwhile switching to.
If some revelation like that were to happen, people would be outraged, they'd demand regulation, and meanwhile they'd continue to use Google/Bing; maybe some would switch to Incognito windows, but that's about it, in my opinion.
What if you build it like a distributed network focusing on anonymity / less centralization / less advertisement. Of course, it will be a completely different business then google, but this kind of search competition could quickly destroy google business.
Of course, crawling, indexing and distributing billions of URL's is not an easy job, I don't say that it can be done by someone over the weekend, but you don't have to be Microsoft at all to be able to do it.
Big companies like Google has a big inertia. Google built a complete industry (the advertising) over their centralized search system, which is very hard to be changed. This is why they are very vulnerable.
Attempting to compete with Google is akin to creating a new, marginally better implementation of a really widespread standard and attempting to market it: nobody is going to use it.
But far less if you don't personalize everything?
Knocking Google off their top-of-the-search-engine perch is likely (I doubt the'll remain an effective monopoly).
Whoever does that though, is unlikely to simultaneously knock them off the online advertising perch, the web/mobile mapping perch, or any of their other major "markets".
None of their verticals in unassailable (I don't think) - but I _very_ much doubt anyone will take them on and prevail in more than one important one at a time - the lumbering all-encompassing tentacled beast that is Google2015 is spectacularly unlikely to be duplicated by a single different player (in my not-so-humble opinion).
Hard to say. Personally I have noticed that they are doing pretty good job at keeping the spam out of my search results. It wasn't so always. Another thing that still amazes me is the almost realtime indexing of web.