Data-validating protocol
Carol generates a NIZK proof common reference string and a statistically binding commitment

to a formal description of $M$. $\:$ Carol sends both of those to both Alice and Bob, and additionally

sends the associated decommit string to Alice. $\;\;$ For each message $m$ in $M$, Alice calculates
the proof of $\:m\in M\:$ and encrypts it along with $m$ before sending the ciphertext to Bob. 

After decrypting, Bob can then verify that $\:m\in M\:$ by verifying the NIZK proof.