If companies like Microsoft adopted end-to-end encryption wherever they can for their services, this would be less and less of an issue. The users from a certain country wouldn't need to "trust Microsoft" anymore then, because there would be nothing to trust them with. In the same fashion, governments wouldn't need to try and force Microsoft to build local datacenters to keep the data there. When the service is trust-less, such policies aren't necessary.
Fair point. I was more meaning that arguments about how he couldn't comply (in that case for legal more than technical reasons) didn't cut much ice. The general view of the authorities appeared to be that the operator of the service was required to comply and if they hadn't left themselves a way to do so without violating some other obligation then that was their problem.
But if there was technically nothing they could do to access the data, they could not be forced to do it. If I encrypt data on my machine and upload it to s3, Amazon cannot be forced to do anything other than provide the encrypted data to the government. They can't be compelled to give my key because they do not have it. It is very hard to operate e-mail this way, because the server cannot send your e-mail other servers in the encrypted form, unless you limit correspondence to users that are using your encryption and key-exchange system.
Not all cloud services have this limitation. However I suspect that there will always be some metadata that the government will be able to request from the cloud provider, and this legal question will still be relevant.
