Mail not delivered from custom email server (MS Exchange)

I have my own Exchange Server 2013 (SP1). I am able to receive emails ok but sending emails is not reliable. Emails sent to gmail or seznam.cz (email provider in Czech Republic) is ok.

The problem is sending emails to outlook.com. I guess it is somehow discarded by spam filter but I don't know why. The delivery report says The message was successfully handed off to a different email system. This is as far as we can track it. but email is not delivered and nothing returns back.

This I have already done:

• set MX record for my domain (aaa.com to mail.aaa.com)


• set A recored (mail.aaa.com to x.x.x.x)


• set reverse IP record (x.x.x.x to mail.aaa.com)


• set TXT record v=spf1 mx a -all



• removed internal hostnames of outbound emails (link)


• set FQDN for send connector (mail.aaa.com)


• set FQDN for FrontendTransport receive connectors (mail.aaa.com)

The mail server is not listed in any blacklist in http://mxtoolbox.com/blacklists.aspx.

Is there anything else I should do? I really don't know where to start looking right now.

Answer

Adding this as an answer : If your mail server is getting a successful SMTP message out, and recipients aren't receiving it, you must ask the people who own the next-hop mailserver. There is literally no other way for you to find out what that mailserver did with what your server gave them. You can guess all day long, and you should (in general) follow best practices and check if you're on DNS RBLs, etc, but it's still just guessing.