>> When we are legally obligated to comply with demands, we pull the specified content from our servers where it sits in an unencrypted state...
Why would the public's private data sit in unencrypted state on Microsoft's servers? What would be the point of encryption if corporation servers can see what you think you are securing via assumed privacy?
(caveat: I'm not a security expert) Encryption is used for data 'in flight' as well as 'at rest'. As far as I know, very few companies/services go out of their way to encrypt your stuff at rest (it's within their systems/firewall/etc at that point). Even if they did, they hold the encryption keys so can 'see' it anyway.
If you want a situation where a company cannot see your data, you have to hold the encryption keys yourself (nb: knowing the password != holding the encryption key. My rule of thumb for this is if I can do a password reset on a service, then that service can see everything I put into it.)
You just create a search index before encrypting the data. Then you encrypt the index. Each time you need to search, you decrypt the index, get a reference to one or more results, fetch those, and decrypt them.
That's trivialising what can become a pretty complex scenario, but it illustrates the point.
I wasn't saying it's impossible, just that it's pretty hard.
That said, I did it in a native client app, where state is easier to maintain.
http://nakedsecurity.sophos.com/2013/05/05/ibm-takes-big-new...