I find BitMessage protocol truly decentralized. I worked on implementing a java client for it a while ago. It stores encrypted message on your machine, although only the intended receiver can decrypt the message. Although inefficient it's impossible to identify origin of the message. On the downside the p2p message propagation could take time. I wish it was more popular.

Source: https://bitmessage.org/wiki/Protocol_specification