Um sauber von einem Webserver aus E-Mail-Nachrichten via SMTP zu versenden, ist ein Reverse-DNS-Eintrag für die sendende IP-Adresse wichtig.
Um bei einem bei Amazon EC2 gehosteten Server einen Reverse-DNS-Eintrag zu erhalten, ist es notwendig, das „Request to Remove Email Sending Limitations“-Formular auszufüllen und abzusenden.
(Das abgesendete Formular erscheint übrigens nicht in Eurer Liste der Support-Cases im AWS-Support-Center. Das geht irgendwie wohl einen separaten/anderen Weg)
Gebt dort die benötigten Elastic-IP-Adressen an, und den Namen des Servers, so wie er im Reverse-DNS eingetragen werden soll. Ihr müsst dementsprechend im Vorfeld schon einen A-Record in Eurem DNS eingetragen haben.
Hier ist eine Antwort von mir im AWS-Forum dazu, und hier ist ein AWS-Blogbeitrag von 2010 zu diesem Thema.