How would you feel about the postal service opening the letters it transports in a similar scenario? Do you think it's morally a-okay for them to unilaterally decide to read your mail without a court order?
I suspect that most people would say "no", even though it all happens on the postal services own premises, using their own resources. At the same time, I wouldn't be surprised if most people would think like you expressed when it comes to e-mail.
Clearly, more thought needs to go into this to determine in a reasoned and consistent way whether Microsoft's action were morally right in this particular instance. Value judgments are going to play a role, too. Still, I think it's fairly clear that the answer must be the same for physical and electronic mail.
Edit: I know you were talking more about legality than morality. However, as the physical mail scenario shows, there is already a legal precedent for an actor being prohibited by law from acting in a way that is analogous to what Microsoft has done; and ultimately, the law should follow moral considerations, so those are the more interesting questions anyway.