explicitly forming relationships

One approach that may be interesting: today, everyone gets to send 
everyone else messages, and every message stands on its own. An 
alternative would be to require the sender and the receiver to have 
some (trust?) relationship before messages may be exchanged. In such a 
setup, relationship establishment would be an integral part of the 
protocol.

Instant messaging services already do this, although they usually also 
permit the exchange of messages without a pre existing relationship.