Sending emails to AWS SES from EC2 with no elastic ip

I'm going to take a guess that you are using sendmail to send the emails, correct?

According to the Amazon SES Docs:

(Optional) If you are sending email through Amazon SES from an Amazon EC2 instance, you may need to assign an Elastic IP Address to your Amazon EC2 instance for the receiving ISP to accept your email. For more information see Amazon EC2 Elastic IP Addresses.)

I'd suggest moving away from sendmail and use Boto to integrate with SES or submit your emails via SMTP to Amazon from your Python app.

Update

The comment from Michael - sqlbot made me think to investigate further, here is what I found.

I remember learning about reverse DNS lookups on email, and found the following:

Amazon now has a new email policy in which outbound SMTP traffic is blocked (beyond miniscule usage). In order to be able to send email directly from EC2 you also need to provision an Elastic IP address for your instance. Amazon will work to keep that Elastic IP of of the common anti-spam lists.

as well as

Amazon has announced a new private beta where they will set PTR records for your Elastic IP address.

Taken from Sending Email from EC2. The article explains all the details in delivering email from an EC2 instance and its problems. Even though it's old, I believe the reverse lookups apply now more than ever to fight spam.