Столкнулся с похожей проблемой. Использую для отправки почты Яндекс.ПДД. Мой IP вроде как чистый (проверил по "47 базам", кажется на 2ip.ru).
Проверял отправку на свои почтовые ящики (mail.ru, gmail.com) - всё ок. Другим пользователям письма доставляются в спам.
Решил проверить домен по "спам-базам", сам он оказался чистым. А вот один из IP-адресов для mx.yandex.net висит в нескольких базах:
Результат:
www.host-tracker.com/InstantCheck/ResultComplete/3...
Или вот скрин:
Куда копать, может кто-нибудь подсказать?
