According to one embodiment, a secure e-mail messaging system includes an e-mail relay server coupled to a secure client configured on a secure domain and an external client configured on an external domain. The e-mail relay server has a memory for storage of an actual address of the secure client, a first certificate associated with the actual address, an alias address associated with the actual address, and a second certificate associated with the alias address. The e-mail relay server receives an e-mail message that includes the alias address from the external client and decrypts the e-mail message according to the second certificate. The e-mail messaging server then replaces the alias address with the actual address to form a modified e-mail message, encrypts the modified e-mail message according to the first certificate, and transmits the modified e-mail message to the secure client.