Nothing seems to help...
by "...extreme measures" i meant:
- contacting ICQ directly and finding out if they have any information that can help - maybe more ports should be opened? did you try that (opening more ports, contacting ICQ)? BTW, try this: http://www.icq.com/help/view_faq.php?faq_id=4737
- try also the forum on ICQ.com - users may know the problem (sorry Yedda)
- considering ICQ2GO - the web flash version of ICQ
- considering using other ICQ alternatives as Meebo - which allows you to connect thru the web to your ICQ account
good luck