Their purchasing power is significantly higher; their dollars are just worth more. We're not talking small amounts, either – a difference of 25% or more in purchasing power is easy to find when you're comparing CA to the South. [1]
So, when you look at it like that... why shouldn't Google pay less? Even a 10% pay cut would amount to Southern workers still making an effective 15% more than their Bay Area counterparts.
Again: I'm playing devil's advocate here. In another comment on this thread, I totally agree with you: the argument of "same work, same pay" is very hard for me to dismiss, and I really don't have any argument against it. I just think there are very convincing arguments in both directions.
Edit: another counterargument for anyone who is stridently in the "same work, same pay" camp: What if you were working at a job in North Carolina, and your company told you that you needed to move to New York in order to keep your job, and they weren't going to give you a pay raise? Do you still feel that "the same work deserves the same pay"?