I've been thinking of ways to combat this as well, and I admit it's an interesting problem. You either have to do some kind of Tor-like onion protocol (which has its own problems), or send every message to every client in the world. Sending your message to [your friend] + X random people would still allow an attacker to eventually gather a very detailed map of your friends by looking at which come up most often.
