Genial! Ya esta funcionando.
Lo que había que hacer era cambiar el servidor qmail por postfix. Lo hice con esta simple linea, segun este tutorial:
http://kb.parallels.com/en/5801 Cita: /usr/local/psa/admin/sbin/autoinstaller --select-release-current --install-component postfix
La razón por la cual el VPS con qmail no entragaba mails a Google la explica Hostasaurus aquí:
http://forum.parallels.com/printthread.php?t=260369
Basicamente, google implementó el protocolo ipv6 en junio, y hay que cambiar el servidor de correos del VPS por eso, para que les lleguen los mails a gmail.