Mail classified as spam, but passes SPF and DKIM

Solution 1:

I think I found two possible reasons why mails are listed as spam.

First, as someone previously suggested (and as I was already aware of), missing PTR for sending server could be main cause.

Second, since this server is hosted in AWS cloud, and Amazon has worked with Spamhaus to add all their IP ranges to PBL by default, it could also be the reason... From what I know, PBL has certain weight in deciding if email will be marked as spam or not. Also, Amazon has blocked requests for removal of their IP's from Spamhaus PBL list directly - requests have to go through Amazon. Luckily, they offer a way to remove Elastic IP from this list, and to setup a PTR record, while you're at it.

So I'll see what happens after this process is complete.

UPDATE: Amazon added correct PTR record, and it didn't resolve the problem. However, after they removed IP from Spamhaus PBL, mails stopped being sent to spam. Meanwhile, many SMTP servers stopped accepting mails from my SMTP because of this PBL list, which was also resolved when PBL record was removed.