Ages ago, I wrote most of an XHTML-IM parser for StepChat. I didn't enable it in the default build, since it wasn't quite working. Over the weekend, I finished it off, tested it, and added support for generating some XHTML-IM. The code is not completely compliant with the specification, since it doesn't bother checking if the other party supports HTML. This will probably be added soon. It also contains a couple of work-arounds for libgaim-based clients, which interpret the standard quite creatively.
Below, you can see a conversation I had with my debugging persona (yes, I know talking to yourself is a sign of madness, especially when you use the Internet to do it). The first image comes from FreeBSD/GNUstep while the second one comes from OS X. Camaelon is not enabled for Jabber on my FreeBSD box because it was breaking things (I think it's fixed now, but I haven't got around to removing the default)
The more observant among you will notice that I fixed a bug in the handling of bold text in the middle of this conversation.