Yahoo had about a $30 billion market cap when Google was just getting started.
Actually, several startups have. Two notables that Google hasn't acquired:
February 2004 - Facebook launches with 0 users. Various folks with dispute the success of Google+ though those disputes revolve around how much of a lead Facebook has.
June 2006 - "google" added to the dictionary.
July 2006 - Twitter launches with 0 users. Google tried to compete with Buzz and shut that service down shortly thereafter.
Sometimes we forget that these household names were startups a mere 5ish years ago, long after Google had established itself as dominant in search and ads.
Read the book What Would Google Do?!
Their business models peaked at the right times and their brand is sticky because the technologies work. They make the complicated world of information on internet simple to navigate. Like the Apple products, it is a tool that anyone can use and feel good about. As long as you listen to your customers and the results continue to be positive, it is hard for anyone to take your market share... even Yahoo!
Perhaps there's another angle to approach this: "How have startups encouraged and enhanced the power of Google?"
Since inception, Google has acquired over 100 companies—many of which would be considered startups. These M&A's are a way for a large company like Google to onboard talent and IP that enhance existing products as well as extend their offerings. An example would be the acquisition of GrandCentral which ultimately became GoogleVoice. They have also acquired several smaller search engines that have gone on to enhance their core offering, as well as protect their market share.