apache 2.2 - Issue with mod_rewrite (possibly related to special characters?)

We have just made a new website for a client and for SEO purposes have a HUGE urlmap setup to rewrite the old site URLs to relevant places on the new site.

Technical details are:

CentOS 5.6 
Apache 2.2
mod_rewrite
PHP 5.3.8

Here is the mod_rewrite block:

RewriteMap urls txt:/www/sites/domain.co.uk/etc/urlmap.txt
RewriteCond %{REQUEST_URI}      ^(.*)$
RewriteCond ${urls:%1|NONE} ^(.*)?$
RewriteCond %1  !NONE
RewriteRule .*  %1 [R=301,NS,QSA,L]

Some redirects do work, for example:

www.domain.co.uk/store/SEURLF/ASP/SFS/PP.Y/RID.577/SFE/Diaries.htm redirects correctly.

www.domain.co.uk/store/SEURLF/ASP/SFS/CATID.1/FORMAT.STUDENT%2FSCHOOL+WEEK+TO+VIEW/ACADEMIC.1/SFE/diaries.htm does not, and 404s. The only difference here is the "+" symbols. This doesn't appear in the rewrite log either, like it's being completely passed over by mod_rewrite due to the special characters.

Another odd occurrence is, for example:

www.domain.co.uk/store/diaries.asp?catid=3 - doesn't rewrite properly, looking in the Apache rewrite log it's completely ignoring the query "?catid=3" for some reason.

I am no expert on mod_rewrite so would appreciate any assistance. If you need more information please do ask.

Thanks in advance!

Edit:

Fixed with:

RewriteCond %{REQUEST_URI}\?%{QUERY_STRING}  ^(.*)$
RewriteCond ${urls:%1|NONE} ^(.*)$
RewriteCond %1  !NONE
RewriteRule .*  %1? [R=301,NS,L]

Answer

Fixed with:

RewriteCond %{REQUEST_URI}\?%{QUERY_STRING}  ^(.*)$
RewriteCond ${urls:%1|NONE} ^(.*)$
RewriteCond %1  !NONE
RewriteRule .*  %1? [R=301,NS,L]

Thanks guys.