Gracias a ambos!.
Estamos investigando si estamos en la lista negra de Gmail, como llegamos ahí, y como salir. Aunque también leí por ahí que quizas haya que activar IPv6 o algo así para poder enviar correo a Gmail. Les suena?
editado: al parecer esto tiene que ver con qmail y no tener implementado ipv6
http://kb.parallels.com/114276