I was just poking around the Google Webmaster Tools and came across a neat idea.  Google has a snippet of javascript you can put on your 404 error pages that will give the user more information based on their indexing of your site.  It can offer a user things like a closest match to the URL they were trying to find, an alternative URL, a link to the site's site map and last but not least, a Google search box that searches the site in question.  You have to have your site setup in Webmaster Tools to use it.