Link rot is only going to get bad from now. It's real, and it's awful.
It's not even random websites. NYT will post a link to a popular Youtube video, two days later the video gets pulled, and one week into the article, the links are already stale.
As Wiki gets more 'reputable', newspapers will posts links to it. Wiki being what it is, the reference to the page will go stale.
So here's an idea for a service: hash all the outgoing/inside pages on a website. If they change, either 1) give options for users to review, 2) update the link 3) delete the reference. If the original website 404's, change the link to the archive page. If a video link is outdated, provide tools to search for similar videos to link, from inside the dashboard. For Wikipedia, automatically link to a certain version of history of a page, not the general page. This is different from the idea posted below because it integrates with existing publishing systems, so it'd be more b2b, and one would start cashflow right away.
For links to social media, use a 'photo snippet' tool that looks to check if the link is valid, and goes to the image version of the link if validity is dead.
I'm certain people would pay GOOD MONEY for this service. I know I would if I were running a publication.
Give me some spare change if it succeeds. : )