On the SitePoint PHP blog today there's a new post showing you how to create a 404 page that will redirect people back to the page they're looking for (that used to be there).

It's often necessary to reorganize your site and change the URL structure but, assuming you have similar content, users should rarely encounter a "page not found" error. Producing unnecessary 404 pages is one of my top 10 development mistakes. In this article, we'll create an automated PHP redirection system that converts old URLs to a new address. It's not production code, but it will illustrate the basics so that you can adapt it for your own website.

They walk you through the creation of a 404 error handling PHP page, configuring your server to use it and making the mapping of new URL to old URL. There's even a bit to include if there's not a mapping for a requested page - returning a 301 HTTP header.