Hola,
Pues lo que pasa es que o tu IP o tu servidor de correo esta listado en las listas de spamers. Puedes probar en
www.dnsstuff.com par ver si esta en las listas.
No se si puede ser simplemente que el usuario concreto que ha puesto en su lista negra, o si es todo su servidor de correo, o estas en las listas publicas.
Saludos.