Concordo com mfinni, você precisa rastrear as mensagens um pouco mais para determinar o ponto de falha.
A primeira suposição é que você não está recebendo nenhum tipo de notificação de falha na entrega (non-delivery report) dos emails que nunca chegam ao destino correto?
Verifique o maillog no seu servidor Linux e veja se ele mostra erros nas comunicações. Esse é sempre o primeiro passo para tentar determinar se são as configurações do servidor que estão causando o problema ou algo sendo retornado do servidor de recebimento. Além disso, você pode testar manualmente o smtp do seu servidor Linux para o servidor de retransmissão SMTP para verificar as comunicações apropriadas. Exemplo de sessão smtp manual (< denota respostas do servidor)
telnet smtp.our-isp.co.uk 25
< 220 saudações do servidor serão vistas aqui
ehlo servername
<250> pode receber várias 250 linhas, dependendo das opções disponíveis
mail from: sendinguser@domain
<250>
rcpt to: recipient@domain
<250>
data
- Esta próxima seção não gerará nenhum feedback, por isso você só atingirá cada linha e a linha final será um período por si só em uma linha (observe que há uma linha vazia entre o assunto e o corpo do email).
From: sendinguser@domain
To: recipient@domain
Subject: Whatever subject you would like
Body of the email goes here, type to your heart's content.
.
Supondo que o servidor aceitou a mensagem, você deve receber uma resposta 250 com algum tipo de confirmação (como "enfileirada para entrega", etc.).
Se tudo isso funcionar, então a mensagem pode estar sendo desligada no ISP, ou silenciosamente descartada pelo seu ISP (o seu IP do servidor Linux está configurado para ser retransmitido através do seu ISP?) ou rejeitado pelo site do destinatário, etc, etc.
Você precisa tentar restringir o quanto seu e-mail está fazendo para tentar obter assistência na verificação de logs de outros servidores envolvidos para os quais você não terá acesso (que é sempre a parte divertida de rastrear um e-mail ).