.local é tão ruim quanto .internal! Você deve usar um subdomínio de terceiro nível que você realmente possui como internal.company.com, onde company.com é seu nome de domínio registrado legítimo da ICANN (ou qualquer outro).
Você está certo sobre não poder renomear o domínio com o Exchange instalado. Depois de criar um novo domínio com o nome de domínio correto, você poderá usar a ADMT para executar uma migração entre florestas de usuários, grupos, computadores e servidores. Você também terá que fazer uma migração entre florestas do Exchange, o que pode ser doloroso, mas há toneladas de ferramentas para fazer isso por você.