Welcome to WebmasterWorld Guest from 188.8.131.52
ErrorDocument 404 /error.php
in your htaccess (if your host supports this)
Then make error.php which should be a 'smart' 404 page which checks what page was requested. If it's an old url that has moved, it 301 (permanently) redirects to the new location. If the page genuinely doesn't exist, it should give a 404 error as usual.