MX Secundário ou DNS Redundante?

Olá pessoal,

De uns tempos para cá venho recebendo várias reclamações de clientes informando que alguns e-mails enviados à partir do gmail não chegam até suas contas. Verificando nos logs realmente não há nenhum registro desses e-mails no entanto para o remetente é retornado o seguinte erro:

---------- Forwarded message ----------
From: Mail Delivery Subsystem <mailer-daemon@googlemail.com>
Date: 2015-10-04 14:45 GMT-03:00
Subject: Delivery Status Notification (Delay)
To: contato@dominio.com.br

This is an automatically generated Delivery Status Notification

THIS IS A WARNING MESSAGE ONLY.

YOU DO NOT NEED TO RESEND YOUR MESSAGE.

Delivery to the following recipient has been delayed:

alguem@dominio.com.br

Message will be retried for 1 more day(s)

Technical details of temporary failure:
DNS Error: MX lookup of dominio.com.br returned error Timeout while contacting DNS servers

O problema é que não ocorreu nenhum problema com o servidor para que ocorresse erro de dns conforme é informado. O servidor é configurado com um domínio próprio e suas respectivas dns e já verifiquei todas as configurações e não encontrei nada que pudesse estar causando este problema que está me dando muita dor de cabeça.

Como está se transformando em um problema constante estou pensando em adotar DNS redundantes via cPanel Dns Only  ou um mx secundário para funcionar como um backup de e-mails, pesquisando na web encontrei um plugin para esta finalidade https://www.ndchost.com/cpanel-whm/addons/pluginsmx/

Algum colega pode indicar qual a melhor solução ou até mesmo uma outra opção ou solução para este problema?