Fair Use is how it *might* (notice that I said "might", I don't want to go through that whole "BigDave said that it was Fair Use" garbage again) be legal.
You have to understand that in the United States, copyright does not exist to protect the creator of the work. The protection is only the means, not the goal. The goal is from section 8, clause 8 of the United States Constitution:
"To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries;"
It is to promote the base of public knowledge. You are granted copyright for the public good, not for your own good.
The public's ownership interest in the copyrighted work was made clear in court cases for well over a century before it was ever codified into law.
If having the cached pages available is a great public good, there is a very good chance that the courts will find a way to rule on the side of the public good.
And believe it or not, the fact that there is a way to keep Google from showing the cached version, will play into any court case given the nature of web publishing.
I'm not saying that it is absolutely legal for them to do, but it is far from being as cut and dry as the average content publisher would have you believe.
I personally think that the wayback machine has a much greater claim to public good than the google cache pages, but I don't know all the arguments that would be made.
I would not be surprised if google were to welcome a lawsuit on this issue to help create caselaw in their favor.