Dashes In the Url Causing 404 Error

I'm working in PHP (5.2.14) on an Apache Server (1.3.33) with MySQL, and a problem has emerged with the pretty url's that produced by our .htaccess file. For example, www.example.com/pages/page will work, while www.example.com/page/this-other-page suddenly does not work anymore. If I type in underscores instead, the 404 goes away, but the page uri's are stored in the database with dashes, so it returns a "page not found" CMS error.

Here are the rewrite rules that put in the dashes.

RewriteRule ^([a-zA-Z0-9\-\_]+)/([a-zA-Z0-9\-\_]+)/?$ page.php?module=$1&uri=$2 [L]
RewriteRule ^([a-zA-Z0-9\-\_]+)/([a-zA-Z0-9\-\_]+)/([a-zA-Z0-9\-\_]+)/?$ page.php?module=$1&uri=$2&sec_uri=$3 [L]
RewriteRule ^([a-zA-Z0-9\-\_]+)/([a-zA-Z0-9\-\_]+)/([a-zA-Z0-9\-\_]+)/([a-zA-Z0-9\-\_]+)/?$ page.php?module=$1&uri=$2&sec_uri=$3&tri_uri=$4 [L]

I suspect there is some configuration rule on the server that does not like the dashes, but it's not on our server. The client is hosting elsewhere, and their server admin has not helped at all.

Or is there a php configuration rule that might fix it?