Apache2/mod_rewrite doesn't properly redirect all URLs

Given the following vhost:

<VirtualHost *:80>
ServerAdmin
ServerName m.facebook.com
ServerAlias *.m.facebook.com

DocumentRoot /var/www/project/web/

<Directory /var/www/project/web/>
Options FollowSymLinks
AllowOverride All
</Directory>

RewriteEngine on

RewriteCond %{HTTP_HOST} ^.*m\.facebook\.com$ [NC]
RewriteCond %{HTTP_HOST} !^m\.facebook\.com$ [NC]
RewriteRule ^(.*)$ http://m.facebook.com$1 [R=301,L]

RewriteCond %{REQUEST_URI} !^/(static)/
RewriteRule ^(.*)$ /index.php [L]

ErrorLog /var/log/apache2/error_project.log
LogLevel warn
CustomLog /var/log/apache2/access_project.log vhost_combined
</VirtualHost>

I'm trying to redirect all requests except those starting with /static (that's where the CSS, JS and images are) to a main controller, index.php, which will handle the routing to different modules.

It all works fine, until I try to access a link like this:

http://subdomain.domain.com/view/10/Http %3A %2F %2F news.discovery.com %2F space %2F nasa-installs-cosmic-ray-hunter

and Apache2 displays a 404 page, the request never makes it to the index.php file. Note that I deliberately put spaces above in the link before %3A and %2F because the forum replaces them with : and / when displayed, but they aren't present in the actual link. Replacing all %3A and %2F in the actual link with something like a dash makes it work again.

Also tried to use:

RewriteEngine on
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule . /index.php [L]

but the same 404 happens.

Any idea what the problem might me?