Descobri que o problema não estava nos registros DNS, mas nos firewalls do EC2. Dependendo do grupo de segurança do EC2 em que você colocou sua instância, o tráfego de entrada / saída pode ser bloqueado em várias de suas portas (incluindo 25, no meu caso).
Eu abri a porta 25 para o tráfego de entrada no painel do AWS EC2 e consegui enviar / receber mensagens com êxito.