Can't deliver emails to microsoft

I have a postfix server, on Ubuntu 13.04. On my domain, I set up correctly every MX, SFP, DKIM and A record.

I've tested them with gmail, reports DKIM and SPF PASSED. So no problems, my mails comes in Inbox with every mail service. Except one. Microsoft.

Microsoft keeps cut my emails off. They can't even reach Spam folder. Now, what should I do to reach Microsoft without forcing my users to add the domain to whitelist?

Test that I've done:

SPF:

http://vamsoft.com/support/tools/spf-policy-tester

http://www.kitterman.com/spf/validate.html

http://www.appmaildev.com/it/spf/

MX, and other stuff:

http://mxtoolbox.com/

DKIM:

GMail

http://www.appmaildev.com/it/dkim/

All of them passed.

Solution 1:

You are sending mail using HELO mail.edennetwork.it and that domain resolves to the correct IP address.

However the reverse DNS (PTR record) for the IP address does not resolve back to the same domain. It resolves to static.193.150.4.46.clients.your-server.de.

You should contact your hosting provider and request that they change the PTR record for that IP address to mail.edennetwork.it. If they won't do that, you should change your HELO to match the PTR record (or change your hosting provider).

You might also want to check that your IP is not on SpamHaus's PBL and read through this.