While Microsoft hasn't announced any plans to modify its terms of service to disallow this type of internal customer data searches in the future, the company does plan to make some changes to the process that governs this type of investigations.
"We will not conduct a search of customer email and other services unless the circumstances would justify a court order, if one were available," Frank said.
In addition to using separate teams for legal review and internal investigations, the company plans to send the evidence that it believes would otherwise justify a court order to an outside attorney who used to be a judge.
"We will conduct such a search only if this former judge similarly concludes that there is evidence sufficient for a court order," Frank said.
The company also plans to start including data about the number of internal searches and the number of accounts they affected in its bi-annual transparency reports that currently include data on searches conducted in response to government and court orders.
Despite the promise of external oversight in the form of approval from a former judge, some privacy advocates don't think such searches are appropriate to begin with.
"We believe that this behavior is in fundamental contradiction with the principles of the Global Network Initiative, of which Microsoft is a leading member," said Joe McNamee, executive director of European Digital Rights (EDRi), in email. EDRi is a pan-European association of digital rights organizations.
"How can they say that it is appropriate for a private company to grant itself arbitrary access to private communications and support the GNI principle that 'Everyone should be free from illegal or arbitrary interference with the right to privacy and should have the right to the protection of the law against such interference or attacks?" McNamee asked.
The Global Network Initiative is a multistakeholder group founded in 2008 whose stated mission is to advance privacy and freedom of expression online. Its members include human rights and press freedom groups, academics, investors, online services providers -- including Google, Microsoft, Facebook and Yahoo -- and other technology vendors.