Problema para enviar e-mail

Boa tarde pessoal.
Estou tendo problemas para enviar mensagens de e-mail somente para um domínio específico. Todas as mensagens enviadas para este domínio estão ficando "presas" na fila do Qmail.

Estive verificando o log, do Qmail, e encontrei a seguinte mensagem:

@4000000048627d260da8066c starting delivery 127: msg 23920655 to remote destinatário@domínio.com.br
@4000000048627d260da80a54 status: local 0/10 remote 7/40
@4000000048627d2e17bd27f4 delivery 127: deferral: Sorry,_I_wasn't_able_to_establish_an_SMTP_connection._(#4.4.1)/

As mensagens que os usuários deste domínio enviam para mim, são entregues normalmente. O problema está quando os meus usuários enviam para esse domínio.

Enviei mensagens para endereços do Yahoo!, IG e Gmail e as mesmas foram entregues normalmente.

Fiz um teste

# nslookup domínio.com.br

onde ele apresentou erro. Tentei o mesmo comando porém utilizando os domínios, por exemplo, ig.com.br e uol.com.br e o comando trouxe os resultados esperados.

Acredito que o problema está no servidor DNS desse domínio. O que vocês acham? Existe mais algum teste que poderia estar fazendo para confirmar essa informação?