When AltaVista suffered a revolt from the users (for up-listing sites that payed them), they had done enough to establish that a search engine needs to be huge (ENORMOUS) to link to every site possible, when given the right search terms. Google the-search-engine probably could never have happened without AltaVista setting a pretty big precedent and trying to cash in. Nobody ever thought Google's first motto "Don't be evil" meant "don't make a profit" and in fact Google floated while still making a huge loss. So many people had used it and found it good, there was obviously going to be some way to make money from it.
A really effective search engine it turns out, doesn't just need to be (in capital and in computer cycles and storage) REALLY HUGE, it also needs to keep growing as the number of sites multiplied. For this it always had to be a for-profit. The idea of some government putting up the money and (without capitalist strictures) getting a decent search engine on that scale, is absurd. Government is fine at building infrastructure, but a search engine is NOT infrastructure. Google grew to fit the conditions, conditions that were unknown (though glimpsed by the likes of AltaVista or HotBot), and are changing still. Without the profit motive directing them, software engineers given a huge budget would never have ventured into that unknown.
So please, no talk of nationalizing Google. Make the bastards pay tax, and if you absolutely must, start building a public competitor. It is nothing but destructive to put the non-profit yoke on a company that isn't done exploring the options for every other company, private or public.