Como Joequerty já disse, aumentar o TTL pode ajudar, desde que os servidores de envio já tenham seus registros armazenados em cache. No entanto, por outro lado, se você precisar atualizar seus registros MX por algum motivo no futuro, quanto mais você aumentar o TTL, mais tempo terá que esperar antes que todos tenham pegado essas alterações. Pode ser um equilíbrio entre os dois e você tem que decidir o que é mais provável que aconteça e, no caso de ser necessário, o que provavelmente causará mais tempo de inatividade.
Espero que esses dois eventos sejam a exceção, e não a regra, mas, pessoalmente, eu estaria pensando mais em mudar o domínio para um host mais robusto do que ajustar os registros MX.