I was thinking about a system that combined these three properties:

    + Anonymous
    + Distributed
    + Encrypted

For anonymous, I was thinking that the service would be accessible only through Tor or i2p, so that neither the sender nor the receiver can be found out by tracing the message.

For distributed, I was thinking that the mail system would essentially be a freesites-style distributed hash table where the mail address (or a hash thereof) would act as the key. The mail or parts of the mail would be stored multiple times across many clients to eliminate single points of failure. Perhaps a TTL system would prevent old mails from filling up everyone's space.

Finally, the encrypted would be achieved by having the mail address act as the public key (or at least, the mail address is a key to a distributed KV store that contains the public key). This way, before anonymously sending the message to the various distributed hash table buckets, it gets encrypted so only the desired recipient can read it.

It seems like it should be possible to build this from already existing technologies without thaaaat much trouble, though I haven't actually done anything about it.

Of course, getting people to use this would be another story ;-) and I guess people would want contacts lists, archives and so on.