Os dados do DNS são armazenados em cache. Se você não reduziu o TTL antes da mudança, as entradas poderão ser armazenadas em cache até o tempo limite.
Se você puder configurar seu servidor antigo para adiar em vez de rejeitar o email que chega da Internet, as mensagens devem ser entregues ao servidor correto. Alternativamente, e provavelmente mais apropriadamente configure o servidor Exim para escutar somente no host local. Servidores legítimos tentam novamente alguns dias antes de enviar o email. Isso deve ser tempo suficiente para encontrar o registro MX correto.