Comment Retroshare solved this half, IRC the other (Score 5, Informative) 109
Okay, first off, the nature of instant messaging is such that you can't truly have an anonymous system. After all, while "the network" may not know Alice, Bob, and Carole, the three of them must know each other and be able to distinguish between them...otherwise you've simply got ChatRoulette and the purpose of IM is largely moot.
Retroshare provides fully decentralized IM, pseudo-email, and file transfers. It's a wonderful tool in this regard. It solves the problem of $IM_SERVICE keeping a record of your chats, because there isn't one. It solves the problem of packet sniffing, because it's all PGP based and thus there is no such thing as an unencrypted packet that enters or leaves the software. It solves the problem of needing a server, because everyone is a peer. All of the things that this Tor program seems to solve, has already been solved, and then some. "Well then,why doesn't everyone use it?" Well, the nature of Retroshare makes it difficult to gain critical mass. You have to understand, at some level, how PGP works - instead of a 'friend request' with that person's actual name, you get to share public keys to 'add' them. This is fine and dandy, but opens up a few new problems. First, even cutting-and-pasting something the size of a PGP key and then reciprocating it to the other person is going to cause the eyes of most people to glaze over. Second, you'll need to exchange keys somehow; if you're e-mailing keys back and forth, most people would say "...so just e-mail the damn message". This is where the file sharing half comes into play, since users can trade files directly without having to do much else. However, with Dropbox/Gdrive/1Drive/etc making transfers stupid simple, the practical application for Retroshare in the eyes of Facebook Chat and Whatsapp users starts to wane significantly when put up against "use an already-functional communication medium to do a PGP exchange that will facilitate another communication medium." Bonus points for Retroshare being a smidge petulant when it comes to port forwarding, and not having a mobile version for any platform.
Conversely, we have IRC. it's ancient, and the UI of mIRC doesn't jive well with the Instagram crowd, but anyone with some semblance of tech skills can run an IRC server. Set that up with SSL and your communications are encrypted, with nothing more than a generic handle to identify you with. The problem is that you'll need someone who can set up such a protected server, and by definition, you have a single point of failure. IRC's other failure (which may apply to Retroshare as well) vs Tor is that IRC does involve IP addresses, so you'll still need a proxy of some kind (or Tor itself) to obfuscate that little nugget.
Tor routing communications through other users as a part of the protocol is the one problem it solves. Secure transmission of text-based messages has been solved pretty well already, "Anonymous IM" is an oxymoron based on the fact that IM in itself usually assumes a prior relationship of some kind between the two parties, and even if it didn't, each user will need *some* sort of unique identifier to ensure that Alice gets messages meant for her, Bob gets his, and Carole gets hers.