1) I'm unclear whether your Exchange server is Exchange 5.5 or Exchange 2003.
2) Yes, an email admin has *potential* to access any mailbox on the server, regardless of the version of Exchange.
3) I'm not sure how encrypting the mailboxes would help - presumably the person who implemented the encryption would be your email admin guy, thus ensuring that he had administrative access to the encryption details... so how would this stop him changing these to access the mailbo(es) still?
4) If you can't trust your admins, who can you trust? Basically, if they aren't honest and reliable and holding 100% of your trust, you have much bigger potential problems that just a few mailboxes being accessed.