g1smd - 3:16 pm on Jan 17, 2013 (gmt 0)
If possible the new URL should use hyphens, not underscores.
This then becomes a simple problem to rewrite (that's rewrite not redirect) all requests with underscores to a PHP script that manipulates the URL and sends the HTTP 301 header and the new URL header OR sends 404 Not Found when there is no new URL to redirect to.
This means the htaccess performance for all requests is quick as the file is short.
The PHP file can be as large or as small as you like, it will only be invoked for requests that need to be redirected.
The PHP file could be as simple as old and new URLs as pairs in an array, or patterns covering multiple URLs in an array, or other logic as required. Whatever you do, Regular Expressions will probably feature quite highly.