RewriteRule ^/red/miasto/.+_([^_]+).html /redirect.php?miasto=$1
RewriteRule ^/red/branza/.+_([^_]+).html /redirect.php?branza=$1
RewriteRule ^/red/marka/.+_([^_]+).html /redirect.php?marka=$1
np.
<a href="http://www.n73.waw.pl/red/miasto/warszawa_cmVtb250eQ==.html">http://www.n73.waw.pl/red/miasto/warszawa_cmVtb250eQ==.html</a>