Proba la IP externa del servidor en
http://www.dnsstuff.com/ en el modulo "Spam Database Lookup". Hace la prueba en un monton de bases de datos de Spam. Quizas sea eso.
Y fijate tambien si Google tiene razon, y no estan saliendo granden cantidades de correos desde tu servidor o desde la IP externa, si es que varios servidores o inclusive salen por esa IP, ya que por ejemplo un virus en una terminal de trabajo mandando mails masivos puede generar esto.
SAludos!!!