I can't remember, but I don't think MSN had offline messages. And I don't think ICQ lost offline messaging in the OSCAR transition, IIRC, ICQ moved to OSCAR with offline messages, then AIM got them, then AIM and ICQ could talk for a while (but all my ICQ contacts that I kept had moved to AIM or MSN by then anyway).

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)