Estas seguro que tienes el registro SPF configurado correctamente? Tu registro spf deberia contener los mx de google y ademas la ip de tu servidor. te dejo una pagina muy util para crear un registro spf
Código:
http://old.openspf.org/wizard.html
Sobrel el tema del hello, depende de que SMTP uses. sendmail/postfix/exim/qmail