As Fastmail, we also recommend that people get their own domain. Being able to move is prudent regardless of how good any one host is! Own your own namespace :) We would rather keep people because we're good, not because they're locked in.
The mail is encrypted at rest to protect against illegal access, not legal access. Fastmail are transparent on what they will or won't do. Where's the problem?
I'd be more worried about a programmer working on the bowels of OpenSSL or LibreSSL etc and being seconded by ASIO/ASIS/DSD than about companies.
I'm a long time (and very happy) fastmail customer and I have no problem with their position. Not because "I've got nothing to hide", but because if I did, I'd know not to use their service.
I depply despise the telecommunications assistance act. I think it's badly written and comes from an inherently uninformed and impractical idea that you can legislate against people keeping secrets. I hope that the reviews in Parliament right now, and, hopefully, the changes to be made under a new Labor government, will remove a lot of the stupidity.
We've seen at least the US government have some fairly expansive requests in order to track down one single person, and they never delete the data once they obtain it. So a copy of those records will forever be outside of your control, potentially without you ever knowing it.
End of the day, if you have a scenario where a third party is the custodian of your information, that custodian has control of it and will follow whatever legal framework that they are obliged to follow.
We are on a grandfathered plan now and are putting off upgrading to a current plan as long as possible because it's a huge price jump to start paying for my kids to have 25 GB of storage which they are barely using.