When a user comes across your site's 404 File Not Found error page, it is most likely not what they were looking for. Here, you have the opportunity to turn a dead end into a resource that can help your visitor find whatever they were looking for.
If you were going to create the perfect 404 File Not Found error page, what would it do? What are the most helpful features of effective 404 File Not Found error pages? Are there any strong examples out there?
If the site has had a recent redesign, and I couldn't prevent the 404 with redirects, I'd probably include a short message about the redesign, and hints for how they might find what they were looking for in the new structure.
I would just make it lightweight and fast loading as possible, with prominent links to a site map and the home page. As soon as I realize I've hit a 404, I usually dive for the back button, or just try to hit the home page of the site if I'm interested enough in whatever it is I was looking for. I almost never actually read what was on the 404 page. Maybe not a good habit, but I bet most site visitors are about as impatient as I am.
If you can be bothered to maintain a list of dead links (i.e. the address of a page you used to host, which is now deleted/renamed/moved) then you will often be able to suggest the correct page to a user who follows a very old link from outside your site.
In some cases you can give a short text explanation to say why that page does not exist any more. Or perhaps you can detect a part of the file path, which allows you to catch 100 different dead links at once.
I have done this sucessfully for a small website, so I don't know how much work it would be maintaining the data for a larger site, or one where there are multiple people deleting/renaming/moving files.
First of all regarding dead links, which were at one time valid, the most effective 404 is actually a 301 permanent redirect to the new URL. Any site redesign should map old urls to new ones, and any CMS that allows the user to edit page URLs should automatically set this up when the URL changes.
Otherwise a good solution is to present the user with search results from your site, based on the keywords present in the components of the URL.
These are the generic solutions, but I'm sure you can come up with your own specific solutions for your site/webapp, e.g. a wiki style site could display an empty editable page to allow the user to create a page at that URL.