RewriteRules repeating part of the match

Question

What I'm trying to achieve is trying to match both the subdomain and the full path in order to redirect to a version without www. in front of it. To do so I use:

RewriteCond %{HTTP_HOST} ^www\.(.+).mydomain.com$ [NC]
RewriteRule ^(.*)$ %{HTTP_HOST}%{REQUEST_URI} [C]
RewriteRule ^www\.(.+)\.mydomain\.com/(.*)$ http://$1.mydomain.com/$2 [R=permanent,L]

This works ok if I request something like:

www.me.mydomain.com/page

It redirects to:

me.mydomain.com/page

However, if I enter:

www.me.mydomain.com/page/other

It redirects to:

me.mydomain.com/page/other/other

It always repeats the part after the first slash. I can't find out what is causing the repetition. ( I actually encountered the problem in a more complex case, but this was the most simple version I could reproduce it with)