I'm working on a site, and its CMS used to save new page urls using the underscore character as a word seperator.

Despite the fact that Google now treats underscore as a word seperator, the SEO powers that be are demanding the site use dashes instead.

This is very easy to do within the CMS, and I can of course change all existing URLs saved in the MySQL database that serves the CMS.

My problem lies in writing a .htaccess rule that will 301 old style underscore seperated links to the new style hyphenated verstion.

I had success using the answers to this Stack Overflow question on other sites, using:

RewriteRule ^([^_]*)_([^_]*_.*) $1-$2 [N]
RewriteRule ^([^_]*)_([^_]*)$ /$1-$2 [L,R=301]

However this CMS site uses a lot of existing rules to produce clean URLs, and I can't get this working in conjunction with the existing rule set.

.htaccess currently looks like this:

Options FollowSymLinks
# RewriteOptions MaxRedirects=50

RewriteEngine On
RewriteBase /

RewriteCond %{HTTP_HOST} !^www\.mydomain\.co\.uk$ [NC]
RewriteRule (.*) http://www.mydomain.co.uk/$1 [R=301,L]

#trailing slash enforcement
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_URI} !#
RewriteCond %{REQUEST_URI} !(.*)/$
RewriteRule ^(.*)$ http://www.mydomain.co.uk/$1/ [L,R=301]

RewriteRule ^test/([0-9]+)(/)?$ test_htaccess.php?year=$1 [nc]

RewriteRule ^index(/)?$ index.php

RewriteRule ^department/([^/]*)/([^/]*)/([^/]*)(/)?$ ecom/index.php?action=ecom.details&mode=$1&$2=$3 [nc]
RewriteRule ^department/([^/]*)(/)?$                 ecom/index.php?action=ecom.details&mode=$1 [nc]

RewriteRule ^product/([^/]*)/([^/]*)/([^/]*)(/)?$ ecom/index.php?action=ecom.pdetails&mode=$1&$2=$3 [nc]
RewriteRule ^product/([^/]*)(/)?$                 ecom/index.php?action=ecom.pdetails&mode=$1 [nc]
RewriteRule ^content/([^/]*)(/)?$                 ecom/index.php?action=ecom.cdetails&mode=$1 [nc]

RewriteRule ([^/]*)/action/([^/]*)/([^/]*)/([^/]*)/([^/]*)(/)?$ $1/index.php?action=$2&mode=$3&$4=$5 [nc]
RewriteRule ([^/]*)/action/([^/]*)/([^/]*)(/)?$                 $1/index.php?action=$2&mode=$3 [nc]
RewriteRule ([^/]*)/action/([^/]*)(/)?$                         $1/index.php?action=$2 [nc]
RewriteRule ^eaction/([^/]*)/([^/]*)/([^/]*)/([^/]*)(/)?$       ecom/index.php?action=$1&mode=$2&$3=$4 [nc]
RewriteRule ^eaction/([^/]*)/([^/]*)(/)?$                       ecom/index.php?action=$1&mode=$2 [nc]
RewriteRule ^action/([^/]*)/([^/]*)(/)?$                        index.php?action=$1&mode=$2 [nc]
RewriteRule ^sid/([^/]*)(/)?$                                   index.php?sid=$1 [nc]




## Error Handling ##
#RewriteRule ^error/([^/]*)(/)?$ index.php?action=error&mode=$1 [nc]

# ----------------------------------- Content Section ------------------------------ #
#RewriteRule ^([^/]*)(/)?$ index.php?action=cms&mode=$1 [nc]

RewriteRule ^accessibility(/)?$ index.php?action=cms&mode=accessibility
RewriteRule ^terms(/)?$         index.php?action=cms&mode=conditions
RewriteRule ^privacy(/)?$       index.php?action=cms&mode=privacy
RewriteRule ^memberpoints(/)?$  index.php?action=cms&mode=member_points

RewriteRule ^contactus(/)?$ index.php?action=contactus
RewriteRule ^sitemap(/)?$   index.php?action=sitemap

ErrorDocument 404 /index.php?action=error&mode=content

ExpiresDefault "access plus 3 days"

All page URLS are in one of the 3 following formats:

http://www.mydomain.com/department/some_page_address/

http://www.mydomain.com/product/some_page_address/

http://www.mydomain.com/content/some_page_address/

I'm sure I am missing something obvious, but at this level my regex and mod_rewrite skills clearly aren't up to par.

Any ideas would be greatly appreciated!