First, you've learned the lesson about planning a site change (I hope).
Second, what you need is a RewriteMap. Unfortunately, you need access to the httpd.conf to configure that as it can easily bring an entire server down for a simple typo (syntax error).
Third, what cd described is what I've been calling "A Poor Man's RewriteMap," a PHP script which can read a database or just a flat file (essentially, just a table with two columns) which should only be used for 404 situations. Kudos to cd for working that out! While the read-a-file isn't a difficult thing for PHP to do, I'd just create an array in the 404.php script to do that rather than read a separate file. Of course, the redirection would entail TWO header("location:...") lines, one for a 301 status code and the second for the redirection.