What counts as already established credibility? I've worked in Search since joining 4 years ago; my experience is fairly similar to Matt's, certainly more like his than certain rather vocal personalities on Hacker News. I don't have a management role at all though I've occasionally served as a tech lead, and tend to prefer engineering or product-design roles.

I was about 3 years out of college when I joined Google. I'd spent 2 years as an employee at a financial software startup and a year founding my own company (which failed, but the postmortem is now the #1 Google result for [failed startup]). I'd also done some moderately impressive open-source/volunteer work: I'd worked on a website in college that grew to 100,000 registered users, I wrote one of the top Haskell tutorials on the web, and I ported Arc to Javascript. Nothing with a huge userbase, nothing terribly famous, but enough to demonstrate that I had solid technical chops.