And I think it's partly because they do do a lot of research, so they get some of the research prestige. With the number of full-time researchers and publication output they have, the research side of Google would rank as one of the larger institutes if it were standalone. See e.g.: http://research.google.com/pubs/papers.html
I think the same is true prestige-wise of other research-heavy companies. Bell Labs was prestigious; being at Microsoft Research is prestigious; etc.
I don't see why doing privately funded research would be any less prestigious. Microsoft Research is arguably the most important operating system research group in existence, like Bell Labs before them. Honestly I would expect these kinds of misconceptions from the general public, but do most people in our field not understand the state of computer science research today?
I think the same is true prestige-wise of other research-heavy companies. Bell Labs was prestigious; being at Microsoft Research is prestigious; etc.