Isso soa como um problema de DNS para mim. Se um MTA não conseguir localizar um registro MX para o domínio, ele retornará ao registro A do domínio.
Isso pode ser difícil de rastrear se ocorrer aleatoriamente, mas você pode tentar usar o smtpdiag ferramenta quando está ocorrendo para ver se ela fornece alguma pista.