ICQ did support offline messages, from the beginning afaik, too. I had a 6-digit uin (485358 or something similar), until it got banned for running a bot (whoops).
To the sibling reply, I think AIM and ICQ did have interop on messages at some point, it was much later than when ICQ moved protocols to OSCAR and TOK though.
I vividly remember being amazed by offline delivery in Jabber, so at least one of ICQ or MSN must have not had it for me to even notice.
As I recall, originally, the ICQ client polled the server via UDP to see if it had any messages, and then you would do peer to peer for online messaging. But when you logged in, you'd get a cascade of the offline messages (uh, uh, uh, uh-oh)
I only remember Skype being "true" peer-to-peer, with your PC randomly becoming a presence/call relaying "supernode" if you had a publicly reachable IP and good connectivity. Different times!
But this was just for messaging (and file transfer), not for presence/buddy list which was all server driven.
In that time frame, few had firewalls or NAT or two computers at the same location, so (server mediated) peer to peer just worked unless you were on a corporate network.
I definitely used quick buddy from computers at my junior college (98-2000), but I don't remember using AIM express.
In any case, Meebo worked using the (back then) advanced, exciting magic of AJAX :)
A pox on Slack.
We were on dialup back then. You could only send messages with MSN if the other person was also using the household landline at the same time.
Yeah Microsoft did not exactly play fair back then. Even Apple today is not as anti competitive as Microsoft was.
Also, I don't recall ICQ being bloated. Maybe it was later on.
I suspect MSN/AIM/YM borrowed the idea within a few weeks or months.