Systems and methods for secure messaging are provided. A sender may encrypt an email message for a recipient. The email message may contain authenticated sender-recipient mapping information. When a recipient requests a client software download or private key from a service provider, the service provider can verify the authenticity of the sender-recipient mapping information. This assures the service provider that the recipient has received a communication from the sender and allows the service provider to provide services to the recipient based on the status of the sender. If the sender is a member of an organization that is a direct customer of the service provider, the service provider may satisfy the recipient's service request.