Minha opinião seria escrever um script Powershell que enumere todos os endereços de e-mail associados a uma caixa de correio e substitua a parte do domínio por seu novo domínio. Como esses são endereços de e-mail, deve ser muito fácil dividir os endereços no símbolo '@' e adicionar o novo endereço smtp à caixa de correio.