One of the first private messaging solutions to come out was BitMessage. With BitMessage all messages are sent to all users. Peers keep messages for a short period of time.
In theory all blockchains can support private messages, but this question is mostly looking for solutions that are "free" and save your message history even if you are offline for years.
What are the pros / cons of each system?