Я думаю, что нашел две возможных причины, почему письма перечислены как спам.
Во-первых, как кто-то ранее предположил (и поскольку я уже знал), недостающий PTR для отправки сервера мог быть основной причиной.
Во-вторых, так как этот сервер размещается в облаке AWS, и Amazon работал с Spamhaus для добавления всех их диапазонов IP к PBL по умолчанию, это могла также быть причина... Из того, что я знаю, PBL имеет определенный вес в решении, если электронная почта будет отмечена как спам или нет. Кроме того, Amazon заблокировал запросы на удаление их IP из списка Spamhaus PBL непосредственно - запросы должны пройти Amazon. К счастью они предлагают способ удалить Эластичный IP из этого списка и установить запись PTR, в то время как Вы в нем.
Таким образом, я буду видеть то, что происходит после того, как этот процесс завершен.
ОБНОВЛЕНИЕ: Amazon добавил корректную запись PTR, и он не разрешил проблему. Однако после того, как они удалили IP из Spamhaus PBL, письма прекратили отправляться в спам. Между тем много серверов SMTP прекратили принимать письма от моего SMTP из-за этого списка PBL, который был также разрешен, когда запись PBL была удалена.