I know this sounds like a technical question, but I am asking from an entrepreneurial angle.
Both Yahoo and Microsoft have been in the industry for decades, but what prevents them from coming up with a similar search engine like Google? Is it because of Google's patents or some hidden algorithm, or lack of brilliant engineers or better marketing?
I think it's going to take a new approach to unseat Google. It will likely happen eventually, but it may take a while.
Google's "big idea" was that links between sites conferred some level of authority, and that if you can count those links, and perhaps apply some sort of additional qualitative metric to them, you can come up with a ranking among sites for a given keyword (or set).
Somehow, someone will need to come up with a new conception of search. Or maybe (likely?) a new concept of finding information on the internet that transcends "search".
A lot of people seem to think that this is somehow connected with the "social graph" the complex network of relationships and preferences that people express using a variety of sites like Twitter, Facebook, LinkedIn, Flickr, Yelp, etc.
But nobody has quite figured this all out yet.
Large companies are often not capable of executing on big new ideas even if they throw millions or even billions at it. This is why startups continue to thrive. Here's some patterns I have seen in big companies that kill big or even modestly innovative ideas:
1) Internal politics
2) Obsessive focus on cost-cutting and aggressive deadlines that results in stifling technical people's abilities to conceive, design, and build a truly innovative system.
3) Hiring less-then-great resources because they are cheap or located in a geographical area where it's trendy to send your work regardless of the results (see #2)
4) Not listening to outspoken people who can critique the company's current direction and provide a new vision. It's very difficult in a large company to walk this line without being perceived as negative or stepping on the toes of "someone important" who made their fortune on the lame tool in question. Only people who are able to smile, remain calm, and not come across as insincere when internally they feel like throwing things are able to do this. Not many innovative technical people have this skill, more likely they get frustrated of not being listened to and leave within a few years.
Using the technology adoption lifecycle as a guide to explain the market conditions (I've been informed that Crossing the Chasm is a bible at Microsoft) - Yahoo essentially missed the boat during the period where the entire industry was "crossing the chasm" - in the period where everyone was getting online.
At that point in time, the game in town was "Portal" - and everyone was rushing towards becoming a conglomerate of services.
Search was an excellent beachhead (another Chasm term) for Google, and Google was perhaps reluctantly pushed into the business as Yahoo was an early investor who didn't acquire it. They also had Terry Semel who was actually building up Yahoo! as a cable TV follow up similar to Ted Turner's model.
There were some advance thinkers who saw the "contextual" advertising opportunity early on - Google having no way to exit after supplying search to Yahoo - jumped on GoTo's (later named Overture, bought by Yahoo) model of auctioning ads.
Google also had excellent founders who had a powerful strategy which when executed, no one was following for a few years - acquiring blogger.com got external traffic and acquiring Applied Semantics offered a way to gist out websites for relevant contextual advertising.
Search competition when Google first came up was AllTheWeb.com (from FAST.NO) (which had briefly replaced Altavista.com) - and it blew it out of the water.
As a startup in a big market opportunity, you'll have to have some contrarian thinking (Larry and Sergey are big fans of Warren Buffett's Berkshire Hathaway, check out their IPO for the references). When everyone is going into Portals - you go into a niche - when everyone is going niche, you go into MegaPortals.
Baidu, a Chinese search engine company also started on a similar path of being a "search supplier" that turned into a portal player now.
As for Microsoft, they have taken years to get into providing "truth" in their search engine - in their early years of search engine, a search for Linux would have the first link pointing back to Microsoft's website - that just wasn't honest and they shot themselves in their own foot. However, they are resilient to have finally overcome its own bureaucracy and paradox to finally go at this market - something which Sony only recently managed to do so after Apple's iPod ate their lunch (Sony had the paradox of both having invested in content and player).
Further reading - The Search
It's not so much that no other company can, more a matter of asking 'Would they get the market share?'
It's not worth investing in when you consider the dictionary now lists 'googling' as a verb for searchin online...
As more people started to build webpages spiders became interesting, to see what was out there. Then there were search engines, and I think Google as number four for the major search engines, but it was a late-comer, but, it had a better idea than Yahoo's idea, and so became dominant.
But, Google is working hard to go beyond being a search engine company, so they created an OS for mobile devices, they didn't pioneer, but they showed what Ajax can be like, and pushed us into Web 2.0.
They are doing what MS should have been able to do, but MS can't really see past their OS, so that will always hinder MS.
Someone will come up with a better algorithm for indexing the web, but if so many people are tied to MS for email, spreadsheet, GPS, cellphones, then it will be hard to overcome for a new company. People are being tethered to Google through very strong branding.
Being better doesn't mean you win. VHS was not superior to Betamax, yet it won out, for example.
How do you overcome the connections people have to Google, in order to get them to go to your search engine instead of to Google?
MS and Yahoo have reputations for incompetence in this area, so people will go to Bing if they can't find it on Google, but they will tend to turn to Google first.
MS and Yahoo would need to fund a new company that has no public connection to these larger companies, and then it can compete as a new David taking on Goliath. Otherwise, the Google/MS battle is Godzilla vs Mothra (two massive creatures that would battle in Japan :)