[a124556]

Something like this? http://www.btcmessenger.com/?page=send just filter it for spam like we do with normal email, maybe an application anyone can run instead of a website that can be taken down.

Also, is there a provable way to generate a public bitcoin address without learning the private key? As a way to keep it fair.

[sounds]

To what you said: yes. Except to not store the messages in the blockchain, which removes the need to generate a bitcoin address.

However, there are some implementation issues that need to be resolved, e.g. on github.