Acho que encontrei dois motivos possíveis pelos quais os e-mails são listados como spam.
Primeiro, como alguém sugeriu anteriormente (e como eu já sabia), a falta do PTR para enviar o servidor pode ser a causa principal.
Segundo, como este servidor está hospedado na nuvem da AWS, e a Amazon trabalhou com a Spamhaus para adicionar todos os seus intervalos de IP a PBL por padrão, também pode ser a razão ... Pelo que eu sei, a PBL tem um certo peso decidindo se o email será marcado como spam ou não. Além disso, a Amazon bloqueou as solicitações de remoção de seus IPs diretamente da lista de Spamhaus PBL - as solicitações precisam passar pela Amazon. Felizmente, eles oferecem uma maneira de remover Elastic IP da lista e configurar um registro PTR, enquanto você está nisso.Então, vou ver o que acontece depois que o processo estiver concluído.
ATUALIZAÇÃO: A Amazon adicionou o registro PTR correto e ele não resolveu o problema. No entanto, depois que eles removeram o IP da Spamhaus PBL, os e-mails pararam de ser enviados para spam. Enquanto isso, muitos servidores SMTP pararam de aceitar e-mails do meu SMTP por causa dessa lista PBL, que também foi resolvida quando o registro PBL foi removido.