Well, I do have a solution, but I don't really like it...
This will replace all underscores with dashes, and redirects with a 301 status code,
which is the 'Moved permanently'. (of course you can use it to replace any other chars too)
Also, it should be the first rule (for ex in the .htaccess file) because the first line is a loop actually, which goes through all the rules again (because of the the N flag)
RewriteRule ^/redirect/from/([^_]*)\_(.*)$ /redirect/from/thisisthethingwedontneed$1-$2 [N,L]
RewriteCond %{REQUEST_URI} (thisisthethingwedontneed)+
RewriteRule (thisisthethingwedontneed)+(.*) /url/to/redirect/to/$2 [NC,QSA,R=301]
Explanation:
First line:
'redirect/form' : the base path or anything you want to redirect from. It should be included in the second part, to be able to match it at the next run of the loop
first part: 'replace (not underscore) followed by an underscore followed by (anything)' an capture the first and last part for later use
second part: insert some text what is likely not found in your urls before the captured first part, then append the first part, then the dash, then the second part
flags:
N : after this, go ahead again, execute all rewrite rules again, but with the altered url
L : if there was a match, stop here (the 2 flags together actually make the thing what you would expect from the first one.)
Second line
Condition for the next rule: execute the next rule only if the previously defined string can be found in the request uri, at least one times
Third line
First part: match and capture any occurrences of the funny string, and capture everything
after it
Second part: append the second part to any path we want to redirect to (and forget about the funny string)
Flags:
NC: case insensitive
QSA: append any query string
R=301: redirect with moved permanently