Se você estiver migrando para o Exchange 2007, isso é dolorosamente simples.
Se você adicionar o novo servidor ao AD adequadamente, quando mover as caixas de correio para o novo servidor depois de uma hora, os clientes se conectarão às caixas de correio realocadas sem problemas. Eles nunca saberão que isso aconteceu (embora os usuários do OWA precisem receber um novo link).
Se você mover a caixa de correio de um usuário enquanto ele estiver conectado, o Outlook 07 exibirá uma caixa de diálogo OK informando que o Outlook precisa ser reiniciado. Quando ele for lançado, ele será conectado ao novo servidor.
Não sei dizer se o mesmo vale para o Exchange 2003 - mas não há risco de adicionar o segundo servidor Exchange ao seu domínio, configurar os conectores e mover uma caixa de correio de teste.