Primeiro, uma cotação joeqwerty obrigatória: " REGISTROS DNS NÃO SÃO PROPULSADOS, ELES SÃO COLOCADOS."
Você poderia testar o novo registro MX criando uma zona em seu servidor DNS usado por outro servidor de email correspondente ao nome do domínio e colocando o novo registro MX nessa zona, "superando" efetivamente qualquer servidor DNS da Internet para o domínio de destino . Em seguida, você pode enviar um e-mail por meio desse servidor de e-mail, de modo que ele use o registro MX especificado na zona hospedada por seu servidor DNS. Naturalmente, isso implica que você tenha controle sobre o servidor DNS usado por esse outro servidor de email hipotético. Isso é um teste tão realista que posso pensar. Convolto, mas realista.
Verifique se você executou conversas SMTP em relação ao novo servidor de e-mail usando TELNET e verificou se o servidor está entregando e-mails corretamente. Certifique-se também de que o servidor, se estiver atrás de um firewall NAT, tenha a porta TCP 25 encaminhada adequadamente de seu IP público para seu IP privado (ou seja, teste-o com TELNET de algum lugar fora de sua LAN).
Se você já fez tudo o que provavelmente é bom para ir.