A less persistent set of founders may have closed up shop and simply said, "Great technology, but the business around search just isn't there outside the context of a portal".
Google incorporated in late 1998, and by 2000 were powering the search results for Yahoo (the biggest website on the internet at the time). They were being paid (and paid well) for that too.
It was the same year (2000) that they implemented search advertising.
Given it only took them 12-18 months (of explosive growth) before they were powering the biggest site on the internet and making money I thnk it's hard to argue they were ever mediovre.
So there was a period of time they viewed the company as a mediocre investment. And at this point they were just Ramen profitable. But they powered through it, and legend has it, that it was one of the Yahoo co-founders that helped convince them to really make a run of it.
My point, what others may look at and call "mediocrity" and say they won't pay $750k for today, may end up in a few years being the fastest growing company in the history of the world.