Самые очевидные вещи:
- Убедиться, что отсылающий почтовый софт формирует все заголовки правильно. Многие почтовые серверы настроены считать письма с некорректными заголовками спамом, иногда даже отсутствие какого-нибудь необязательного заголовка сразу относит письмо к спаму.
- Убедиться, что отсылающий софт всё правильно делает на сетевом уровне. Например, дожидается ответа от сервера-получателя, прежде чем закрыть соединение. Многие почтовые серверы считают письмо спамом, если отправитель закрыл соединение раньше чем положено.
- Убедиться, что если от сервера-получателя получен ответ "временно недоступно", то софт-отправитель попробует отправить письмо ещё раз через несколько минут. На многих серверах настроен graylisting, который сводится к тому чтобы всех незнакомцев отлупливать с "временно недоступен", в расчёте на то, что сервер спамера не станет пробовать ещё раз.
- Убедиться, что с mx-записью в DNS всё в порядке (настроена обратная зона на DNS, имя сервера во From: правильно ресолвится итд). Тут уже даже не многие, а подавляющее большинство серверов откажутся принимать сообщение, если с DNS у отправителя что-то не так.
- Настроить и проверить правильную работу протоколов аутентификации отправителя: DKIM, SPF. Многие сервера считают подозрительными письма, у которых с dkim или spf что-то не так.
Типичный "спамерский" софт, как правило, игнорирует некоторые или все из этих "советов": экономит на размере заголовков, заполняя только самые необходимые, закрывает соединение сразу после передачи письма, не утруждается обработкой временных ошибок.