Thanks for the replies. I too thought maybe the parenthesis issue was to blame, and so I focused on it for a while... Turns out, it was something else. Notice the difference:
BEFORE (doesn't work):
Options +FollowSymLinks
RewriteEngine On
RewriteCond %{REQUEST_METHOD} ^trace$ [NC]
RewriteRule .* - [F]
RewriteCond %{SCRIPT_FILENAME} !-f
RewriteRule ^((en|de|ru)/[a-z0-9-_]+)\.php$ /$1/ [NC,R=301,L]
RewriteRule ^((en|de|ru)/[a-z0-9-_]+)$ /$1/ [NC,R=301,L]
RewriteRule ^(en|de|ru)/([a-z0-9-_]+)/$ /index.php?lang=$1&page=$2 [NC,QSA,L]
AFTER (works! --
http://czechpoint101.renefournier.com/en/home/ ):
Options +FollowSymLinks
RewriteEngine On
RewriteCond %{REQUEST_METHOD} ^trace$ [NC]
RewriteRule .* - [F]
RewriteCond %{SCRIPT_FILENAME} !-f
RewriteRule ^((en|de|ru)/[a-z0-9_-]+)\.php$ /$1/ [NC,R=301,L]
RewriteRule ^((en|de|ru)/[a-z0-9_-]+)$ /$1/ [NC,R=301,L]
RewriteRule ^(en|de|ru)/([a-z0-9_-]+)/$ /index.php?lang=$1&page=$2 [NC,QSA,L]
Yup, the only thing I changed was the order of the underscore and hyphen in the last two rules. Can anyone tell me why this fixes the problem? The Apache 1.3 docs are incredibly verbose, and I couldn't find a specific reference on this type of thing, although my suspicion is that having the hyphen and then the underscore maybe makes mod_rewrite treat it as a range instead of a character?
...Rene