試してないけど。
RewriteRule ^/(%[0-9A-Fa-f]{2}|\+|[0-9A-Za-z_.-])+/$ /search?q=$1