I can't believe that they would have so much negotiating power that there's no way out for Google. Even if it's moving them to be the VP of janitor closets.
1. potential reputation and organisational damage that such a person can bring to an organisation without carefully managing the situation;
2. in a company as big as Google (and frankly, one that is doing as well as Google!) it may take quite a lot of time to truly uncover the damage that a person is doing to an organisation, especially if that person is on good terms with upper management;
3. At a high enough level of management in a big enough company, lawyers and professional negotiators can wangle some amazingly good terms into the manager's contract. This can make it exceptionally tricky to remove this person quickly, or even move them sideways (if you move someone sideways, then you change their authority on a variety of things, which almost certainly changes their job description and thus their contract. This goes double if you demote them, even for the same money).
I can't speak for anything going on at Google of course, but I guess I can speculate that it might have been a combination of all three of these things. Which is utter speculation, so feel free to duly assign it the value that you feel it is worth :-)