Here's what i learned:
the connection filter in o365 Exchange is an inclusive list not an exclusive list. Instead of telling o365 "only except mail from these servers" it tells it "always accept mail from these servers".
Somehow, probably through a phshing attack, one of our users had her password compromised. An attacker then used her account to relay phishing e-mails through our O365 server.
Since it was a relay, it didn't show up in her sent items and they added a rule, probably through OWA, to send her incoming mail to deleted items. That way if any of the recipients screamed, we wouldn't hear them