ICQ killed compliance with the old (original) icq protocol. Most of the ICQ clones are not compatible with ICQ2000 (ICQ2000 is basically the same as the AIM protocol). Using a client with the old protocol will cause many strange things to happen. You will have messages sent out through the server that will never reach their destination. Or, sometimes you will keep getting the same message over and over.
Remedies: GAIM, use the Oscar protocol for ICQ. Because ICQ2000 is the same protocol as AIM you could just switch the protocol over and it will work fine. To do the switch just go to Tools -> Accounts and then modify the Protocol settings.
The later Licq clients are suppose to be compatible.
Centericq [konst.org.ua] is ICQ2000 compatible. Centericq is a term based client that works well. No fluff, no GUI, but it is easy to use. It is very easy to install, with low dependencies. The author is a nice guy too.
Ickle [ickle.sourceforge.net] works. Though it seems to want to launch a gnome panel if you are NOT in gnome at the time of use.
Kopete [kdedevelopers.net] is ICQ2000 compatible. I haven't tried it.