Aha. You didn't mean rewrite at all. "Rewrite" means that the user asks for one URL and you secretly serve them content living at a different URL. Here you're talking about changing the URLs of pages that already exist.
If you rename your pages, update the links and don't redirect people asking for the old URL, you lose all the accrued benefits of the old name (rank, link juice, etc.). AND you'll slam into Duplicate Content issues as soon as the search engines discover that you have two different pages with the same name. Or, if they notice the 404s, the search engines will get suspicious and will wonder why you've dumped an old page and replaced it with a new page that is identical.
If you feel that you must change the URLs, the normal course would be to redirect all requests for the old lowline form to the new hyphen form. You might want to remove the old ones from google's cache; no need to remove the URL from the index, since search engines will immediately pick up the redirect.
With only 25 URLs, you can easily do the redirect right in htaccess. In Apache, the pattern would be-- don't cut and paste, this is off the top of my head--
RewriteRule ^([^_]+)_(.+)$ http://www.example.com/$1-$2 [R=301,L]
with more details if some of your URLs contain more than one hyphen/lowline.
But at this point your question is branching into two different directions: the "google SEO" direction, and the "apache" direction. (Or possibly the IIS direction.)
:: looking vaguely around for nearest moderator ::