Apologies for any nativity here, but wouldn't storing encrypted messages on a blockchain be a robust solution for this?

Why would you want that? The last thing I'd want in a secure messenger is a permanent ledger that holds message content and associated metadata which anyone can analyze.

edit: I didn't downvote you and I don't think someone asking an honest question like this should be downvoted