Try matching agaist the request instead of the %{QUERY_STRING}
RewriteCond %{THE_REQUEST} \?CATID=4
RewriteRule ^index\.php$ http://www.oursite.com/map-france/? [L,R=301]
RewriteCond %{THE_REQUEST} \?CATID=5
RewriteRule ^index\.php$ http://www.oursite.com/map-italy/? [L,R=301]
The rewrite engine loops until the URI stops changing, that means your first rule adds the query string, and you second rule matches the query string and redirects to without the query string. Then the browser makes the same request again, and your first rule gets applied, then the second rule matches against the query string and redirects the browser again, etc.