Based on a recent plugin he's developed, Cal Evans has posted this new tutorial on how to use it in a 404 plugin for WordPress to give the visitor more relevant information even when they don't find what they wanted.

One of the things I’ve always hated about WordPress is the stock 404 error message. Out of the box, WordPress just tells users "I’m sorry, I can’t find what you are looking for." Granted it is better than the stock Apache 404 page but it isn’t much more helpful. Having just finished working on the Bing Search Wrapper for PHP, the best use case I could think of for the wrapper was to solve this particular problem. This is how I helped Microsoft’s Interoperability team to put together the Bing 404 Plugin for WordPress.

He includes two ways to do it - either watch the video for a quickstart or you can follow the "gory details" on how it all works and how/where to implement it in your WordPress insallation's code.