You cannot truly protect mail from the Exchange admin if they have Exchange Domain Org/Enterprise access. If their intent is malicious, they can bypass delivery methods, and impersonate users, bypassing transport encryption.
PGP would work for receipt only and in the case the sender is also honoring the PGP methods needed. An admin could email the person back as the user and say "my PGP is screwed up, can you send that unenecrypted" and 9 out of 10 times, the sender would comply.
Any cloud method is going to fall into this category as well. In order to effectively administer most systems like they, the admin will have keys to the kingdom. You can have auditing in place that would at least monitor administrative abilities so you could see other people accessing mailboxes or impersonating users and then you can require access to these functions. Exchange 2013's DLP (data loss prevention) has gone a long way since 2010.
https://technet.microsoft.com/en-us/library/jj150527(v=exchg.150).aspx
I would start there so IF someone was trying to be malicious, you could track it. But again.... if they wanted to, they can turn this off and be on their way before the other admins find out. You either have to have strict contracts in place that give you massive legal repercussions against the hosting provider, OR choose a provider that is complying with compliance requirements. They have to have auditing and process control in place that would make it MUCH harder for admins to carry out malicious duties.
TLDR;
There's no perfect method to prevent a full admin from being malicious for most mail applications.