Although now that I think about it... twitter probably often suffers from the exact same issue, although somewhat mitigated as people often include the original tweet in their reply.
Using average read/write times for a message - taking its length into account - it should be fairly easy to check if someone could have read and written a response to a message. Assuming it is a response if he could have written one in time should be fairly accurate.
You could probably even cheat and use a constant time while still getting good results.
"[4] I think I once heard of an MSN chat transcript dataset that was really awesome, but I can't seem to find mention of it anymore. Let me know if you know where I can find that or any other instant message datasets. I know that some IRC rooms get publicly logged — is there a single place where one could grab all of them at once?"
You could use pre or post filtering to weed out connect/disconnect and other noise.
I only thought of this because there was like two "TWSS" replies in the past couple of days on #rubyonrails
Reading this post I remembered a small project called sociograph a friend of mine created. It's an IRC bot that logs messages and draws a graph of the people communicating with each other in realtime, see for an example http://www.youtube.com/watch?v=A_ah-SE-cNY.