We started to receive a few support tickets from 365 clients late last week, advising of email bounceback reports they were receiving. We asked for some samples of these and got the likes of this;
hotmail.com couldn't confirm that your message was sent from a trusted location
These errors were come back from HOTMAIL.COM, HOTMAIL.CO.UK, OUTLOOK.COM, OUTLOOK.CO.UK, LIVE.COM and LIVE.CO.UK domains.
Strange - all our 365 domains have SPF set up - and by default we also enable DKIM signing in 365.
Turns out the problem was simply a missing _dmarc record on the domains in question. Assume Microsoft have tightened up their own security settings, and have decided that no dmarc record means no delivery.
Simply adding _dmarc in monitoring only mode is enough to cure the issue.
We've rolled out that fix to all our 365 clients this morning and that takes immediate effect.
New default _dmarc record is simply v=DMARC1; p=none;