Trabalhar com um segundo mx é definitivamente o melhor caminho para você:
Crie uma segunda entrada mx que tenha o novo endereço IP, mas um menor número de preferência. Enquanto o primeiro mx estiver disponível, nada acontecerá, mas os servidores DNS já armazenarão em cache o segundo mx. Assim que você trocar os IPs, o primeiro mx não estará disponível, e o servidor de e-mail será - após um curto período - tente o segundo.
Defina o tempo de DNS para viver de seus registros mx tão pouco quanto possível, em seguida, após a mudança basta alterar as preferências das entradas mx ou remover o endereço IP antigo completamente.
Dessa forma, o máximo que pode acontecer é um atraso de 5 minutos na entrega de correio, pois esse é o tempo padrão, alguns sistemas aguardam antes de tentar novamente, mas a maioria dos sistemas tenta o segundo mx imediatamente se o primeiro não estiver disponível .
E com relação às entradas de DNS: na verdade, você pode configurar um registro A para ter mais de um endereço IP. Isso é chamado de "DNS round robin". MAS: Os navegadores na maior parte do tempo usam o primeiro endereço IP na lista e só mudam para o segundo após 30 segundos. Isso só pode ser reduzido se ambos os endereços IP estiverem ativos ao mesmo tempo ...