Preserve the privacy of the metadata of messages — who is talking to whom — by pre-signing a certificate. Include a certificate authorized by the recipient with any encrypted (private) message. That way we can encrypt the message's author, but leave the recipient visible.
Our service can then be sure that a message is allowed (not spam), but we cannot see who is sending the message, because that is encrypted.
Because the recipient remains visible, we can stay practical with storage and message delivery. We can reject messages for a person that we don't care about, and deliver messages efficiently to users we do care about.
Thanks @Dominic for sketching this idea.
See also
