Eu uso o EC2, e depois de alguns problemas iniciais tive sucesso razoável com e-mails. Se você não for usar um serviço externo, algumas sugestões:
- Use um Elastic IP (e não o altere com frequência) - acho que este é o maior deles - um IP em constante mudança não leva a nenhuma confiança no remetente
- Verifique algumas das listas negras comuns de e-mail - a maioria tem uma opção de remoção de lista manual. Se o IP que você está usando estiver listado, peça a ele para removê-lo (ou obtenha outro IP elástico que não esteja listado).
- Configure seu DNS corretamente, incluindo registros MX e um registro SPF
- Assine seu e-mail usando DKIM / DomainKeys (sugiro DKIMproxy)
O DNS reverso é importante - mas os IPs do EC2 apontam para uma entrada de DNS que mapeia de volta para o IP, portanto, mesmo que não aponte para o seu domínio, não parece contar com um.