An apparatus in one embodiment comprises at least one processing device having a processor coupled to a memory. The processing device implements a messaging policy enforcement server that receives from a first client device metadata of an encrypted message to be sent from the first client device to a second client device. The received metadata comprises a first key utilized by the first client device to encrypt the message with the first key being encrypted utilizing a second key associated with the second client device. The messaging policy enforcement server processes the received metadata to determine one or more policies applicable to the encrypted message and to generate a further encrypted version of the encrypted first key utilizing one or more additional keys corresponding to the one or more policies. The further encrypted version of the encrypted first key is sent to the second client device in modified metadata of the encrypted message.