Depois que o novo servidor de e-mail estiver pronto para aceitar e-mails para seu domínio por meio do smtp e enviar e-mails via imap e ou pop ou semelhantes, você deseja alterar o servidor antigo para encaminhar e-mails para o novo servidor. Faça tudo isso funcionar ANTES de alterar os registros MX. Então, não importa se o e-mail chega ao servidor antigo ou novo, pois tudo acaba no novo servidor, eventualmente.
Eu não gosto de pessoas que usam o termo "propagação" quando me refiro à maioria das alterações no DNS, pois acho que a maioria das pessoas está sendo enganada sobre o que está acontecendo. Normalmente, as alterações de DNS são instantâneas, não há necessidade de propagação. A propagação só acontece quando você está alterando os servidores de nomes no registrador, e essas alterações precisam sair para todos os servidores DNS raiz. Esta é uma operação que costumava levar muitas horas no passado (padrões distantes da internet), mas não leva mais tempo. Atualmente, quando as pessoas falam sobre propagação, elas geralmente estão se referindo incorretamente aos TTLs do DNS.
Sempre que um servidor de nomes autoritativo responde a uma pergunta DNS (como quais são os registros mx desse domínio), essa resposta vem com um TTL, que diz "aqui está sua resposta. Você pode assumir que essa resposta é a resposta correta por X segundos ". Portanto, se você tiver um TTL muito longo nos registros MX e, em seguida, alterá-los. As pessoas que pesquisaram seus registros MX podem armazenar em cache os resultados por um longo tempo e, portanto, após a alteração, enviarão mensagens para o servidor errado por um longo período. Se você está antecipando uma mudança nos registros DNS. Você pode soltar o TTL para algo pequeno até depois da mudança.