Forum Moderators: Robert Charlton & goodroi
The reason this usually happens is that your server is not returning a 404 status code in the http header - that's the information the server sends to the user agent before it sends the page's visible content.
This has been called a "soft 404" and the fix is just to return the actual error status code in the http header. You can use Firefox with the LiveHTTPHeaders add-on to inspect all the http header information going back and forth between a user agent and your server. This will help you to be sure when you have it right.
For example, in the Diagnostics, for "mydomain.com/error/401" it shows "401/407 authentication error" under the detail column... same for all the other error pages.
@LifeinAsia: I think your suggestion would work