My sister Jenni and I have a lot of IM sessions with very rich structure: lots of tangents and a real need to maintain a stack so as not to miss anything. Even when I'm IMing with other people, there are frequently multiple threads going on at a time and it is sometimes difficult to follow which response goes with which thread.
For a while, Jenni and I have been talking about writing a tree-based instant messaging client - a real-time threaded discussion client.
This weekend, we were able to come up with a usable prototype using Python, wxPython and Jabber.
Stay tuned for more information as development continues.
UPDATE (2004/04/16): Michael Lawley has just told me about http://tickertape.org where "there's a whole family of IM clients supporting threaded discussion."