We had a similar issue with Microsoft email on our own custom mail server. Microsoft delivers mail for several domains from the same email service, so this similarly affects email from outlook.com, hotmail.com, live.com and msn.com. See https://postmaster.live.com/pm/policies.aspx for details.