Changing URL encoding behavior / 301 redirection

I have been using SEF Advance on my website for approximately six months now. It is configured to use the Title as URL with spaces converted to underscores (_). Exampe:

Title: Three ways to make your URLs SEO friendly
URL: www.mysite.com/three_ways_to_make_your_urls_seo_friendly.html

Recently I found out that underscores are interpreted as keyword connectors by google while hyphens (-) work as keyword dividers (see http://www.prweaver.com/blog/2004/08/26/2-hyphen-and-underscore for details).

Due to the fact that the keywords in my titles are usually supposed to be interpreted as separated keywords, I would like to change SEF's encoding behavior so that it uses hyphens instead of underscores. Fine - but here's the problem:

Once I change the encoding behavior, all URLs in my website that have been indexed by google so far will not be reachable anymore. My options are either to redirect to a 404 site or to my front page - both result in being removed from the index due to availability or double content.

Is there any way to make SEF redirect the old underscore URLs to the new hyphen URLs automatically, sending a 301 (moved permanently) header to make google just update the URL instead of removing the entry  completely?

Example:
www.mysite.com/three_ways_to_make_your_urls_seo_friendly.html
-> moved permanently, redirection to:
www.mysite.com/three-ways-to-make-your-urls-seo-friendly.html
-> and then the normal mod_rewrite redirection to the article as before.

What would you recommend?

Thank you for your responses!

Well this is the problem related to any attempt to change configuration of your URLs in a late stage.
When you do configurations you should do it before your website has been indexed by search engines and not change the format later.

There is no automatic redirection for URLs that supports changed URL settings. The only redirection engine built-in in SEF Advance is redirection from old-style SEF URLs to SEF Advance URLs.

There might be, however, some ways to make redirects you need using some mod_rewrite or htaccess magic. Or it could also be added to PHP logic. That can't, however, be covered by regular SEF Advance support.

So, if you can't solve it yourself, you may contact me to estimate the costs for a custom programming for you.