And here's another thought about that - just delete all messages from the blockchain after they're read, and only store them locally in the clients. As soon as the receiving client unencrypts the message, store it locally, then delete it completely from the blockchain. Unlike bitcoin, this wouldn't be an accounting ledger with the necessity of storing all transactions in perpetuum. All that needs to happen is the message get delivered to its recipient, once that is verified to have happened, it can be deleted. The clients can keep copies and organize them into conversations or whatever.
That wouldn't quite solve the issue of hardware eventually being able to brute force the encryption though, since an interested party could store a running record of everything put into and deleted from the blockchain. But it would have to be a very interested party to store that amount of data in the hopes of being able to decrypt it years or decades later.
Bitcoin wasn't really designed for deletions though, and that would also double the rate of blockchain diffs, so would have to think more about how or if that would work...