Every web site needs a test and QA policy.  This begins with your initial editing and release cycle: development, stage, production, and continues after release with the steady testing of your site.

There are many useful link validation tools available on the web.  Basic delivered/not found crawlers provide useful free reports like http://www.brokenlinkcheck.com/.  More sophisticated application level testing and reporting is also available from many vendors for a fee.  Tracking the errors is usually the easy part.  Correcting the errors is a thankless, labor intensive process.  

One thing is for sure, be sure to replace the default 404 series error files on your server with user friendly recovery navigation pages.  This will still disappoint the visitor but at least it won't be a complete dead end.