We're pleased to announce that the Live Search folks released a new toolkit today for creating dynamic 404 error pages. The Web Page Error Toolkit allows you to display custom error messages with search results that are generated from relevant keywords. Rather than generic "We're Sorry" pages with links to every subject area within your site, these custom error pages offer relevant choices to help your visitors find the information they want.
Note: A new version of the toolkit was published on 8/26/08 to
remedy a security matter found during an internal review. We recommend
you download the new toolkit and recreate your custom 404 pages to safeguard the security of these pages.
According to the Live Search blog,
The Toolkit is a customizable ASP.net application that replaces the default
error page on your IIS server. The Toolkit enables you to use Live Search (or
any search engine) to return results for the specified domain and locale,
control the number of results returned on your page, choose whether to offer
spelling corrections, and customize your error message.
Take a look at these examples of a typical 404 error page at Microsoft, as well as one that has been customized with the Toolkit:
Typical 404 Error Page

Dynamic 404 Error Page
The Live Search team has a nice write-up here. Check out the following links for more information: