Circa 2000 or so, when AIM, MSN, Yahoo! and ICQ were all flourishing, Yahoo had already added offline messages. ICQ, I think also had them, though it was probably configurable, I recall the client having a half dozen screens of options. At that moment, neither MSN nor AIM had it yet. AIM eventually did add it, though I don't recall if it was added to AIM after ICQ de-merged from the AIM backend.
There was also Meebo, which allowed you to login to all of them via a web interface (which I believe none of the messengers had natively) without installing the respective clients!
Meebo was sick. I remember they never made any money though as an IM webapp, and eventually fully pivoted to some kind of on-page ad toolbar that site owners would add to their sites...for some reason.