IMO the best method would be to use a custom 404 page. So put
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.