You do have recourse, and it certainly can be illegal.
Just because corporations have a Russia-in-Crimea style boots-on-the-ground advantage when it comes to the cloud doesn't mean you have to throw up your hands and give up when someone violates your rights.
What's the basis for this assertion? The privacy policies seem to have clauses that allow this type of access. The user wilfully enters an agreement to utilize Microsoft's email servers and that agreement explicitly allows this. Even if it didn't, I don't know of any body of law that would say "the text you're uploading to another person's server can't be read by the server's owners", but I'm not a lawyer. Telecomms are different because their infrastructure is a means of conveyance, not a destination, so they need to file the paperwork to tap the comms between the source and the destination. But in this case, there is no unannounced party in the transaction.
If we assume there are no external legal modifiers, it seems pretty straightforward that the server owners should be able to search their own disks for any reason.
The entire premise of free modern email is that the provider will be automatically parsing the text of your emails, composing a profile of your behavior and interests from that text, and attempting to sell you products based on that profile. Wouldn't that be illegal if it's not legal to search your own disks? How come you can agree to ToS and privacy policies that allow that but not policies that say "we can also look at it if we suspect that you're trying to screw us over"?
As a society, we put a limit on which kind of contracts are valid and enforceable. To give an extreme example, if you write into a contract that you sell yourself into slavery, that contract would be invalid and not enforced.
Most countries have similar limitations for consumer protection. For example, Germany has a certain minimum warranty that a manufacturer must provide that cannot be waived away no matter what they try to write in the ToS-style contracts that exist for businesses here (AGB).
Contract law is not a physical law. It is shaped over time - ideally in a way that follows a consensus of all citizens in a democratic society. If we feel that morally, webmail providers should not have the right to do targeted investigations in their hosted mailboxes (which is easily distinguished from the kind of algorithmic scanning for marketing purposes), then that can (and should) be turned into law.
Just because corporations have a Russia-in-Crimea style boots-on-the-ground advantage when it comes to the cloud doesn't mean you have to throw up your hands and give up when someone violates your rights.