Orbot (Tor for Android) allows you to host hidden services on your phone. My ideal IM app would be one which uses Tor to enable peer to peer delivery of messages over Tor hidden services directly between phones.
This way, not only would the message content be safe from pyring eyes, but nobody would be able to see who is talking to who or when.