Check all the links on the web pointing to you and if needed redirect them 301 or notify webmasters to change the link.
For the rest follow the message #5 here from incrediblehelp.
There is nothing wrong with the code 404 for anything that don't exist on your server and have no valuable incoming links.

__________________
Impossible? You just underestimate the time.