Demora exatamente 0 segundo para os registros MX se propagarem ... porque os registros DNS não se propagam.
O que você precisa pensar é quanto tempo dura o TTL para o registro MX e o registro A correspondente. Isso determinará por quanto tempo um cliente DNS que já tenha resolvido o registro MX e A manterá essas informações em seu cache DNS (que estaria no cliente DNS e em seu servidor DNS correspondente).
Todos os clientes DNS que ainda não resolveram os registros MX e A consultarão seus servidores de nomes e obterão os novos registros MX e A imediatamente, portanto, nenhum atraso de cache TTL ocorrerá.
EDITAR:
Minha intenção não era iniciar um debate semântico sobre a definição da palavra propagação e sua relação com o DNS, e sem insistir nesse ponto por muito tempo, simplesmente declararia que apenas um cliente DNS que solicita informações de sua zona DNS obter essa informação. O cliente DNS vive em uma bolha. Não sabe nada sobre o seu DNS até e a menos que seja solicitado. Mesmo se você considerar que o servidor DNS de um cliente DNS pode disponibilizar as informações para seus outros clientes DNS, ele não o fará até ser solicitado a fazê-lo. As informações de DNS não são propagadas ou disseminadas para qualquer cliente DNS que não solicite isso. Quando o TTL expira, as informações são liberadas do cache do DNS, para nunca mais serem vistas ou usadas novamente, a menos que o cliente faça uma nova solicitação. Não faz mais nada com as informações além de armazená-las em seu próprio cache. Outros clientes DNS do mesmo servidor DNS que consultam as mesmas informações o obterão do servidor DNS solicitando, não pelo servidor DNS, propagando ou disseminando-o.
Podemos discutir se a propagação de palavras, como é usada em relação ao DNS, é um termo vagamente definido com o entendimento de que todos nós realmente queremos dizer cache quando dizemos propagação, mas no final do dia é incorreto O uso da palavra, implicando um mecanismo que não é empregado, e como evidenciado por sua pergunta, é mal entendido e, portanto, "propaga" um mal-entendido de como o DNS funciona.
Independentemente do que você ou eu achamos que a palavra propagação significa, seu uso no contexto da sua pergunta está incorreto.