[amjd]

There's an existing add-on that (kind of) does this. It checks Google Cache and Internet Archive, among others.

https://addons.mozilla.org/en-US/firefox/addon/resurrect-pag...

[greglindahl]

Yes, there are a bunch of plugins which kind of do this. We're hoping to get this into all browsers, and only offer to take the end-user to the Wayback if we actually have a good capture of the URL.