When I did a similar transition with hundreds of thousands of links. I created a database table with source and destination columns. Then a script that handles all 404 requests. If the requested link matches an entry in the source column, the user is sent a 301 to the matching destination entry. That allowed for easier maintenance than a huge htaccess file and the server load caused by te script should go down over time as 301 are saved and you contact site owners to update links. The other benefit is that you can do enhanced tracking to see what is request, found and not found and where those people came from.