I think we, as technologically included people, tend to overestimate how old the internet is to most people outside of maybe early email usage.
Also the implosion of companies (like Yahoo) is a factor here. If Yahoo hadn't been really stupid they would still be dominant - and it would have been hard to stop them.
Of course people can overtake when the leader throws the lead... but it's luck and also hard.
MySpace vs Facebook happened after Google rose to dominance.
Also, Google Video vs YouTube.
I think you forget just how FAST Google blew up. In 1999 they were basically nothing - by 2004 they were the largest search company on the internet.
Facebook wasn't even a thing until 2004 - after the Google IPO. So no, Myspace vs Facebook didn't happen after that.
Also Google Video was just plain crap. It's like comparing Google+ to Facebook, it was never going to last.
Remember though that accurate results is a clear market winning feature - we've seen that the average user quite simply doesn't care about privacy that much.