Bing404 transforms your standard "We can't find that" to "Maybe one of these is what you are looking for".
Using the Bing Search library, this plugin will intercept your standard 404 page and return a list of urls that may help your user find the content they are looking for. You can limit the search to just the content on your site, set a default search in case the computed one doesn't return any results, and set a host of other options, all designed to provide your users with quality recomendations.
This plugin should work out-of-the-box with most themes using the included 404 template. You can also define your own to fine tune the look and feel to match your theme.