Thanks for the heads up - as I said in the OP, it really is a difficult task. Those kind of laws are exactly what need to be avoided when choosing a country to host in. I don't believe that this kind of thing can be carried out in absolute silence though, so if a country is actively modifying and silencing hosts it's fairly likely that word of it will leak somewhere.
If I get a chance, I might try to put together a red/orange/green overview of known laws and practices in different countries that would affect hosting services there. Unless someone is already working on that and needs a hand?
It's up on github, so hopefully everyone can submit pull requests with data and we can crowd source ourselves a very informative map.
https://github.com/Ryan-ZA/hosting_safety_map
EDIT: I also submitted a link to it on HN. Hopefully interested people will see it and can help out with data.
We have a great privacy commissioner ( http://www.priv.gc.ca/index_e.asp ) but the office holds no power so far as I can see, and the Canadian government has a pretty solid track record of being obsequiously cooperative with u.s. interests
Cooperative with U.S. interests is generally assumed by almost any country - this map is more about the (hopeful) safety of your servers in data centers in different countries.
And Germany has also laws which force every mail provider to install an access point to the German authorities and intelligence agencies. I am not sure if also a generic saas platform would have to do it, but it is quite possible.
Better pick Switzerland or Island.