ICQ protocol wasn't published at first, but people reverse-engineered the protocol when the only client that was available for Linux was That Big, Slow, Ugly And Buggy Java Client®.
When reverse-engineered (first by Magnus Ihse), the v2 protocol turned out to be quite horrible. Apparently, the latter versions of protocol, as well, sucked similiarly but differently.
For long time, the passwords were sent unencrypted. The connections were almost always over UDP, making it (without any precautions in place against it) spoofable, hijackable, and not guaranteed to be reliable - and also difficult to deal with in places with firewalls. Also, the client developers noted the official clients were crashy when fed some bad packets...
The clients had "hooey permission bits" - you can set the permission bits all right, but the client is not required to honor them. One of these permission bits is "require authorization in order to add me to your contact list". Well, I edited my mICQ contact list and the "unaddable" users got to my contact list all right... and the users didn't even get a confirmation message that I had added them! Same thing with Everybuddy, I'm not sure if Jabber also did that...
The newer ICQ protocols have fixed the UDP problems effectively by getting rid of it and using a new, hopefully better protocol.
And since the aquisition by AOL, the new winds blow: Newest versions have apparently switched to use AIM OSCAR protocol. (thanks, fuzzie.)
(Oh: My UIN is 4291042 - I hadn't even read Douglas Adams' books yet when I first used ICQ... Though, these days I use only Jabber: wwwwolf@jabber.com.)