This is an often repeated fallacy, but Australia doesn't have the equivalent of the National Security Letter, by which they can coerce any company to do what they want without the right to disclose such breaches. The NSA is also the worst adversary you can get. I doubt Australia's agencies are as competent or as well financed.

Also, no security agency is above the law, but the problem with the NSA is that the US law does not apply to non-US citizens. Us foreigners, the ones that the NSA are supposedly targeting, have no way to fight this through the judicial system and we have no representatives to call or vote. But choose a service provider closer to home and things change dramatically.