Comece lendo os registros de e-mail em /var/log/mail.log
. Se deveria lhe dizer se o e-mail já saiu do seu servidor e se ele saiu, foi aceito pelo GMail ou não.
Verifique também se mailq
retorna alguma coisa para você.
Você pode enviar e-mails com sucesso para qualquer lugar que não seja o GMail?
EDITAR após sua própria edição : algo está bloqueando o tráfego de saída do seu servidor para a porta SMTP (25). Isso pode ser devido a configurações do iptables em seu servidor, configurações de firewall em outro lugar ou então você tem essa conexão, você precisa usar o seu host de e-mail ISPs como host de retransmissão.
Muitos ISPs bloqueiam conexões de clientes para: 25, já que é assim que spammers e botnets tendem a enviar spam.
Minha segunda edição: é o smtp.hutchcity.com
, que não permite que você envie mensagens por ele. Entre em contato com seu ISP.
Minha terceira edição Agora que dei uma olhada mais de perto, seu servidor parece enviar o helo como localhost.localdomain. Isso pode deixar seu servidor de email ISP chateado. Corrija isso, tente novamente, entre em contato com o seu ISP se a correção do seu nome de host não ajudar.