Bonez:
Personalmente creo que tenemos muy confundido los conceptos de lo que es un Servidor de Correo.
Un verdadero servidor de correo, se inicia con la compra de un dominio y la instalacion de un servidor de DNS. Se instala el servidor, se consigue via tu ISP un reverso de la IP donde esta instalado el servidor, se establecen los SPF records en el servidor de DNS, se establecen los MX records en el Servidor de DNS... ETC.
Me confunde mucho esta frase tuya:
"No sé si podrá ser eso o no, aunque como ya te digo, es lo primero que pensé, luego fui a mirar la configuración del correo (uso Qmail), y veo que está todo bien respecto a la seguridad, inclusive SPF."
Los SPF records son competencia exclusiva de los servidores de DNS y No de los servidores de correo.
Si tu Qmail es un autentico servidor de correo, entonces debes tener los LOGS que te diran porque X o Y correo ha sido clasificado como SPAM o rechazado.
Si tienes un firewall, envia un correo y observa la salida por el puerto 25 y a que IP conecta, seguidamente revisa a que entidad corresponde esa IP y de ahi continuamos.
Saludos
Y espero te ayude
Franco
P.S. Una cosa es tener un verdadero y autentico servidor de correo Versus enviar correo utilizando un servidor externo de correo. El 90% de los casos se utiliza servidores externos, Ya sea de tu ISP, de algun servicio profesional, etc; en cuyo caso la clasificacion de SPAM o el rechazo del correo es problema exclusivo del dueño del servidor de correo.