ICQ used to be really frustrating for firewalls. It didn't have any set port that it used, and opened up a random new one on a different port for each person you talked to. This meant that you have to open up close to a thousand ports in your firewall, or at least did. You could force it to play nice, but it usually involves sending all your messages through ICQ's server, which is kind of dumb when you consider that ICQ is (or was) based in Israel, so that's a long trip. Actually, the Mac version was fine with firewalls for the very fact that it only sent through ICQ's servers.
Another stupid thing about ICQ was that it used to not check the address of an incoming message, to see if it came from the person you're talking with. For example, you could receive a message from your rich Uncle Bob saying that he's dying and you are his sole heir. So ICQ opens up a special port for receiving messages from Uncle Bob. People made programs that would find the ICQ ports that were open, and they could send messages to that port, so that ICQ would think Uncle Bob was sending you a message to go stick your head in a blender. Then you tell Uncle Bob to go screw himself, and Uncle Bob immediately takes you out of his will.
Anyhoo, I think a lot of this has been fixed in the past year or two with ICQ's version 7 protocol, fortunately.