Вы смотрели историю своего IP в сервисах вроде spamhaus и подобных? Может, им раньше злостные спамеры пользовались?
Обратный DNS у сервера, с которого отправляются письма, указывает на ваш домен или же на что-то невразумительное вроде 19393.28.clients.someservice?
Причина (кроме технических моментов вроде обратного DNS и SPF) может быть также в содержании письма, тексте, ссылках, их количестве и куда они ведут.