I once read a post on Smashing Magazine about 404 Error pages, and here is my take on what 404 pages should and should not be.
State clearly that it is a 404
Yes, the internet audience for some vague historical reason understands what a 404 page is.
Clear Page not found title
... because not all of them do recognize the 404. It comes down to the type of audience you are trying to serve. Twitter's audience may all know what a 404, 200, 500, 666 error is (what's 666?!). But the Canadian embassy in Sydney cannot rely on that.
Space, lots of it
This page has to have unusual white space around the content or header. It has to be identified as an "unusual" page, because it certainly is unusual to land on a 404.
I do not like those 404 pages that look like any other page on the system. Removing the navigation and providing other ways to navigate is certainly safer than putting the same navigation bar in place. Users need to know it is out of the norm that they landed on this page, so that they try to do something about it.
Not too many exit points
It is confusing to get to a 404 after clicking on a link of the myriad of links you have on a site, it is more confusing to have to correct your own path! So don't ask the users to make more decisions than what they have to.
Sometimes it is possible to identify the source of the 404, for example; a link to a product, in this case you can lead the user back to "products list." But most of the time, 404 errors are generated by external traffic leading to your site, to pages you removed all together. It is not easy to guess the intentions of the users. The safest thing to do, is give them a welcome back to the main door.
You can have tracking code in place to find out about your 404 errors. [Useful read: Optimizing Error Pages: Creating Opportunities Out Of Mistakes]. But a contact form for those who really want that piece of content back, would give you a priority scale to identify which link to fix first. Remember, sometimes, robots find your missing pages, which is something you shouldn't be too bothered about, but you need to filter against, not to end up with too many error reports.
That was a quick and short blog, its Friday!