Use o SES. Grandes faixas dos blocos de rede do EC2 estão mais ou menos permanentemente na lista negra (ou severamente penalizadas) por vários provedores de e-mail importantes. Os nós de extremidade do SES residem em diferentes netblocks que (pelo menos no momento) não estão na lista negra em larga escala.
Dito isso, mesmo que o seu e-mail não seja spam, você precisa verificar se ele não é exibido como "spam". Certifique-se de incluir links de cancelamento de assinatura, etc.