What Microsoft should have done is obvious: Get the case before a judge and get a search warrant. Use the search warrant to access the communications.
Just because you own the email servers doesn't mean you get to play judge and jury.
Microsoft: “Judge, we demand that Microsoft turn over these emails.”
(that is, can you even procedurally attempt to force discovery against yourself?)
Not to mention that the EULA seems to pretty clearly cover exactly this scenario.