For the longest time I thought the web.config was all you needed to tweak to get the whole "page not found" thing working right:
<customErrors mode="On" defaultRedirect="/ErrorPages/ErrorPage.aspx">
<error statusCode="404" redirect="/ErrorPages/PageNotFound.aspx"/>
But it turns out I was wrong! When I was debugging the HTTP headers with the Live HTTP Headers Firefox plugin I noticed that when you hit http://example.com/NonExistentPage.aspx, you got a 302 (redirect) and then a 200 (OK). You never get a 404!!!
The problem with not getting a 404 is that search engines do not remove the pages from their indexes unless they see a 404 when crawling your site. 302 actually means "The requested resource resides temporarily under a different URI".
After doing a google search, this turned out to be a common problem. And the fix was easy. On your Global.asax’s Application_Error method, add the following:
Exception lastException = Server.GetLastError();
if (typeof(HttpException) == lastException.GetType()
&& lastException.Message.Contains("does not exist."))
this.Response.StatusCode = 404;