<< Go grab the latest LICQ snapshot from CVS and compile it. The problem with the one you can get as a binary (1.0.3) is that it only supports ICQ protocol v.6 while windoze version is up to version 8 (2001b) now. For some interesting reason AOL/ICQ decided not to deliver messages through the server from older clients.. Not sure if that's the problem you had, but with most people now using firewalls, messages through the server are becoming the only way to communicate.
When you use Gaim, you are still using the same ICQ library that LICQ uses, so I'd start with a fresh compile of an LICQ CVS snapshot.. >>
There's the problem! I know crapsolutely nothing about Linux and installing programs in Linux, much less COMPILING them myself! :Q
-RSI