Criando um .htaccess do tipo:
RewriteEngine on
RewriteRule ^categoria/subcategoria/detalhe.asp?tipo=detalhe&ar...=([0-9]+) /subcategoria/$1 [L,R=301]
Isto iria redirecionar todos os links antigos para os novos links ....
O exemplo que meti é muito alargado.. nao quer dizer que funcione metendo logo assim, talvez precise de mais alterações ..