We've had great success with SimpLite. Of course both participants must have it installed. It's basically a local proxy. A secondary app that runs local on your PC and listens on 127.0.0.1 and then MSN/AIM/YAHOO/ICQ connects to it and from it out to the servers.........
I'm sure this can be obtained with Gaim and two plug-ins you can get for it, OTR and gaim-encryption. Then you can use any chatnet encrypted like such.