Thought it was Pidgin, but might have been ICQ... it was a long, long time ago that I used any of these... can't remember specifically; maybe even MSN via Pidgin. Seems like it would have been more a function of the protocol that you were using than the client/plugin specifically (naturally that had to support it, too, but the more fundamental would have been the protocol.)
Definitely at the very least ICQ had it - remember freaking out friends by replying to their questions before they even clicked send. This was late 90s...
I'm a bit older and also remember this as well. I would watch in real time when my friends would type something out, or call out their mistakes in typing. I believe you're right about it being ICQ.