I've been working on a similar problem this week, a website I've taken over has 4,000+ broken links because the site was migrated away from an old CMS, so all the URL's are different.
The only way I've managed to solve the problem is by adding a fair number of new Redirect rules to my .htaccess file. What you will find is that a lot of your old links can be grouped together and directed to one section of your site. So for example, instead of writing rules to deal with links like:
Redirect permanent /news_article/01 http://www.mydomain.com/news/01/
Redirect permanent /news_article/02 http://www.mydomain.com/news/02/
You would instead divert these URL's like this:
Redirect permanent /news_article http://www.mydomain.com/news/
So essentially everything contained inside the
/news_article folder would direct to the
/news/ folder of the new site.
It's not a glamorous fix, but either way you are faced with a long drawn out process of redirects.