> ...and the result is that the servers have a plaintext log of who talks to who on their service

Is there a reason why a user's address book can't be encrypted as well?