I would like to advocate for us offering the ability to customize the Page not Found for our clients. If we can do that, then we don't need to add the redirects for cached pages to the server ... and we can provide a helpful post that includes links to search and/or commonly used areas.
Implemented for clients on the new hosting! All clients will eventually have this capability once each has been moved to the new hosting environment.
Note: Dennis is going to disable Fast 404 on the new hosting and we'll be able to recreate the custom 404 nodes like we used to.
Note: there's also an outstanding ticket for Dennis about this :)