Lo que deberías hacer es implantar servicios de identificación para proteger la reputación del dominio.
Sender-ID
Esta tecnología desarrollada por Microsoft permite confirmar la autenticidad del dominio desde el que se envía el correo. Está basada en un estándar IETF: RFC4406.
SPF
Sender Policy Framework también es una norma de verificación del dominio del remitente. Está basada en RFC4408 y consiste en añadir al DNS del dominio un campo SPF o TXT que contiene la lista de IP autorizadas para enviar correo desde ese dominio.
Registro DNS inverso
La resolución inversa permite traducir una IP en dominio. Esto permite encontrar el dominio asociado a una dirección IP.
DKIM
Esta norma se describe en la RFC4871.
AOL, Google (Gmail) trabajan sobre este sistema.
DKIM