we use MS EXCH 2k10 with Postfix frontend and there is a major issue with DNS resolution of mail.protection.outlook.com domains on Postfix servers. These servers are using BIND 9.9.5 nameservers. Sometimes (and this is interesting, it does happen just sometimes) there are outgoing mails in Postfix queue with this status:
(Host or domain name not found. Name service error for name=XXXX.mail.protection.outlook.com type=A: Host not found, try again)
Just mail.protection.outlook.com domains does this. Digging this domain ends up with SERVFAIL but after some time it returns NOERROR with correct IPs from this domain. Then I have to manually flush Postfix queue to send this messages asap.
Not an advisor, but our client with an account at outlook.com have the same everyday repetitive problem. Some outbound messages during the HELO-EHLO conversations go from servers with names which have not corresponded IP address in DNS records.