What should a site do when you try to access a page that doesn't exist?

What happens when I try to visit Nick's Huffpo article about Rap Genius (http://www.huffingtonpost.com/nick-antosca/jay-zs-empire-state-of-mi_b_346636.html), but I get the URL wrong (say I try http://www.huffingtonpost.com/nick-antosca/jay-zs-empire-state-of-mi)?

This isn't a great solution:

1. The lack of design clearly brands this as an "error page". This is visually unpleasant and it makes the user feel like he's done something wrong
2. Why not show me the results of your suggested search query (the first of which is the article I want) on the "page not found" page itself, rather than making me click "Google Search" first?
   

Your site's 404 page should be functionally identical to its search page, with the search query constructed intelligently from the URL.

Here's Huffpo's search page:

Why not throw this on the 404 page?

This is what we do on Rap Genius. For example, if you try visiting http://rapgenius.com/cam/get/em you'll see:

Better still, if your search only has one result (e.g., you tried http://rapgenius.com/cam/get/em/daddy) we take you directly to it and you don't see the "Something isn't right" page at all.

This approach has the added benefit of making it easy to visit a specific song. For example, if I want to go to Jadakiss' "Why", I can just type "http://rapgenius.com/jada why" in my address bar.

There was once a time when a URL had to correspond to an actual file on a computer somewhere*. Fortunately this is no longer the case. Therefore, web designers should stop building applications that interpret user requests for URLs as requests for specific documents and instead as requests for the web application to "do the right thing".

* This is why you still see so many URLs that end in ".html". URLs should never end in dot anything -- there's no technical reason URLs need file extensions and they're just noise for users