Why not remove websites that are 404'd -- using server headers? Although, I guess it would be a hassle to run on a million URLs (bandwidth costs, CPU time costs, etc.)
Maybe allow a user to submit a broken link, check its headers, then allow the user to remap the URL. Potential for abuse? Probably. :/