But Google knows the contents of each page, though. If they were going to be awesome about it, they know what the page says, so they can just store an MD5 hash

But Google knows the contents of each page, though. If they were going to be awesome about it, they know what the page says, so they can just store an MD5 hash of it, and find what the new URL is, if it's still live, or serve a cached version if they can't find it. That'd be pretty nifty.