Amazon probably provides PTR records for all of their IPs. You can check with the host command on Linux:

host 10.1.1.1

You'll also want an SPF record for your zone:

http://www.openspf.org/

DomainKeys are being checked by some webmail providers, but it's only a non-spammy characteristic at this point, not mandatory for delivery. As long as nothing else about your message is stupid (e.g. RFC compliant SMTP server, reasonable DNS records, and you aren't sending 100 per minute to addresses in the same domain), it'll go through.

I'd suggest using whatever Python library will allow you to send using a real SMTP server (or just pipe your email into the mail or sendmail command, which use the local smtpd to send, by default), like Postfix or Sendmail. There may be a standalone library that is actually RFC compliant and handles error conditions properly, but it seems unlikely from a historical standpoint (most such libraries, particularly in the PHP world, are renowned for epic failure). As long as Postfix or Sendmail are configured properly, your mail will be RFC-compliant and will look far less spammy than those coming from a half-assed implementation of the spec.