Imagine putting error messages on a spectrum, according to how easy to understand they are. "404" lies on the cryptic end. "Page not found" lies somewhere in the middle. I think the middle is a good trade-off between designer effort and user satisfaction. But what lies on the other end? This:

We recognize that our website used to present a challenge, and that many people have memorized the path through the maze or bookmarked the information they need. Unfortunately, due to the new organization of our website content, those trails of breadcrumbs and bookmarks will no longer work. We apologize for "moving the cheese" at the end of the maze, but we think you'll have a much easier time finding the information you need.

Our website content has been organized into a number of related categories, listed below. Please Contact us if you need any further information

The above is a real error message I got on this page, and from a government agency no less. Someone is either over-zealous, or getting paid by the keystroke... The worst problem is that you don't immediately realize this is an error page, so you waste time trying to make sense of that paragraph... Yay usability.

By the way, the Internet Archive can be a great resource when you need to dig up a dead link. If the website is "important" enough (I wonder according to which criterion), the Internet Archive will probably have a stored copy. I've found my article here. Another trick for recently-removed content, or for content that's temporarily down, is to search Google's cache (one, two).