Este produto pode ser útil:
É como mod_rewrite (para o apache), exceto que você tem que pagar por isso (não, eu não trabalho para a empresa que o desenvolve).
Para usá-lo, você deve escrever regras que redirecionam a estrutura antiga para a nova. Dependendo das alterações feitas, isso pode ser extremamente fácil ou ridiculamente demorado.
ATUALIZAÇÃO:
Veja: link
RP (permanent redirect)
Almost the same as the [R] flag but issues 301 (moved permanently) HTTP status code instead of 302 (moved temporary).
Exemplo:
RewriteRule ^/my-super-product\.html$ /Product.aspx?ProductID=123 [RP]