My concern with them is that they don't store email encrypted at rest and being an Australian company their laws allow the government to put back doors in and are not obliged to tell their clients.

The government law is out of their control but not having your emails at rest unencrypted.