I had several people tell me that while they liked the idea, they didn't want to install WordPress just so they can have intelligent 404 errors. Several other people pinged me and suggested a way that you could use the Bing Search API to handle 404's without WordPress. As a public service, I am going to try and bridge the gap between these two groups. Going on leads provided by friends, I have hammered out a solution that works with Apache and PHP.
The solution uses a custom 404 page (as set in Apache) that pulls in the "top ten" links from the current site as reported back by the Bing.com search engine. With the help of the API making a request and getting back an object to loop through is simple. This could easily be adapted to accept terms based on the content page that they were trying to find or some keywords based on your site's content.