Google Webmaster Tools has a very interesting widget to improve the usefulness of your 404 pages with little or no effort. It brings something like ?Did you mean?? for your URLs, suggests links like pages in a higher hierarchy, and adds a Google Search form.
http://devthought.com/tumble/2009/04...s-with-google/