Help needed with permalinks now that I am a convert

My permalinks used tolook like this:

domain.com/archives/2005/03/a_post_title.php

Now, after working it out as far as I can they look like this:

domain.com/archives/2005/03/a-post-title.php

So I’m getting loads of 404s from Google searches on old posts.

As I see it there are two alternatives:
1. add a rewrite rule to point people looking for #1 above to #2 above (I don’t know how to do this!) or
2. change the post title so it is ddisplayed with hyphens and not underscores.

Can anyone help me with either?

Thanks in advance