I can't speculate on the reasons why Mark was fired. But two things seem certain to me. One, Mark's a nice, well meaning, intelligent guy (he has to be!) who displayed poor judgement in bad mouthing about Google when actually he liked his job. Second, I can imagine how his co-workers would have rallied against him inside the company for showing Google in such poor light publicly when they all loved it so much. I even hinted at such a possibility before Mark was fired.
If I managed a tech firm in Silicon Valley, I'd have offered Mark a job as soon as I heard the news. Why? An ex-Googler is out of job, does anyone need a better reason? That doesn't happen everyday as Google has remarkably low attrition rates. There is no greater accomplishment for a tech worker in the Silicon Valley today than to be hired by Google.
It's well known that they have an extraordinarily tough recruiting process at Googleplex and they go to great lengths to attract the best talent. Google has contacts in all the major universities in the US, both, to spot emerging technologies and emerging talent before anyone else does. They make regular visits to universities as well, they hold contests, crazy banner ads, publicise the fun and meaningful working at Google -- all so that they maximize their chances of hiring the best people.
As someone said in the Analyst day webcast, Google is even willing to compromise their expansion plans because they can't hire enough people of the exceptional quality they seek. That shows the kind of commitment they have to hiring. I'd be crazy to let go of this opportunity. The kid made a mistake and he's learnt.
ps: I photoshopped that image from two different images taken by Dennis Cheung, another MS blogger present at the meeting.