Cita:
Iniciado por tobaria 
Deberías revisar también si los correos son enviados desde la misma dirección ip (de tu conexión a internet), si es así tomar la dirección IP y pasarla por la busqueda de los filtros de antivirus para confirmar si esta reportada en una lista negra. si es así pues hay que darse la pela y solicitar que sea deslistada. Aca puedes averiguar [url]http://mxtoolbox.com/blacklists.aspx[/url]
Muchas gracias, me has dado la causa del problema. Resulta que la ip del servidor compartido donde estamos estaba listada en spamcannibal.
El problema no es que se haya enviado spam desde ese servidor sino un problema de configuración de PTR no única o algo así.
Este es el mensaje:
Your host is in a spammy netblock and has a missing, generic, or identical (non-unique) PTR record. These IP's are NOT eligible for removal until provisioned with a distinguishing PTR record. This is the most common reason for refusal of removal requests. Don't waste time requesting removal of IP's with generic or missing PTR records. Provide a distinguishing PTR record or configure your mail host to use your ISP's smart relay.
Están los del hosting en ello a ver si lo solucionan.