How to check if a mail server is flagged as SPAM by GMail?

Go to http://postmaster.google.com/ and sign up there, this is recommended by Google https://support.google.com/mail/answer/188131 for blocked emails.

Google provides you there with your individual scoring of your IP and domain.

Verifying your domain also has the side-effect, that you get a higher scoring on your emails.

Also make sure not to send very short (one word) test emails or random strings (like the often used "uname -a | mail ..."), as those are being scored badly.

Google has it's own filtering system, they don't use public blacklists. It's really hard to tell if you have any configuration issues with the most important data commented out.

Your SPF is fine, it passes, I agree it should be -all but that's not the issue you're facing.

From what I can tell you're using AmazonAWS - Which from my experience I always had delivery issues with them and had to stop using them. But this was a couple years back, not sure if anything has changed.

Your best bet to figure this out, without posting the real headers will be to run it through an email tester.

If you don't see any configuration issues, then it's most likely the reputation of the amazon AWS IP blocks, causing the issue with gmail. You can do inbox testing to gain a little more insight into the problem and where else there might be transactional delivery issues.