That's exactly what happened to us. I'm not the only one having email sending issues with EC2, there are several articles about the Spamhaus, EC2 issue.
Use an SMTP server external to EC2 for handling mail sending. I first tried to use gmail, but gmail alters the sender address, so that all messages appear to come from gmail, not quite what I needed.
- Add a relayhost entry to postfix (for me this was in /etc/postfix/main.cf)
relayhost = mail.otherserver.com
- On the host that will be acting as a relay (in this example mail.otherserver.com also in the /etc/postfix/main.cf file), I added the reserved ip address for my EC2 instance to the mynetworks list
mynetworks = 127.0.0.1/8 126.96.36.199 #where this represents the ip of my ec2 server
After running /etc/init.d/postfix restart on both servers, no more blacklisting issues.
The problem with this is that I end up needing to have a server outside of the cloud, which brings a single point of failure and works against the scalability of cloud based solutions.
Hmmm, wonder if I could run my smtp server in Google App Engine, somehow.