I’ve been meaning to put together a write-up about this, but essentially I had to contact Mailgun’s customer support and open a ticket. Their solution was to upgrade me from a poor-quality, poorly-rated shared IP to a better shared IP. Until this point I’d been wracking my brains for several days trying to figure out why things weren’t working.
Not sure if this would be relevant at all to your situation with AWS.