Skype gondok tűzfal mögül

Üdv,

A probléma a következő:
adott egy kis cég belső hálózattal, ami tűzfal mögött van. A tűzfalon az 1024 fölötti portok nyitva vannak, ahogyan a 443-as is. A 80 zárva. A netezés proxyn keresztül történik azonosítás után. A kliensek WinXP és Win7 gépek. A megfelelő személyeknek Skype is van a gépén. A netezéssel nincs is gond, azonban a Skype csak félig működik. A Partner felvétele esetén egy üres ablak jelenik meg azzal, hogy nincs élő internetkapcsolat, ellenőrizzem. A skype fórumán sok tanácsot olvastam, mindet meg is próbáltam, de nem oldotta meg a problémát. Fogtam egy laptopot és rácsatlakoztam vele a Vendég hálónkra, ami közvetlenül megy a netre, se tűzfal, se proxy. Ebben az esetben teljesen működik a Skype. Tehát elvileg csak tűzfal gond lehet. A Skype fórumán azt írják, hogy a Skypenak nem okoz gondot a tűzfal, ha nyitva vannak az 1024 fölötti portok és a 443 vagy a 80. A kommunikációval nincs is gond, csak új partnert nem tudunk felvenni. Próbáltam még a Skypeban megadni a proxy adatokat is, de sajnos az sem oldotta meg a dolgot.
Szóval, találkozott már valaki ilyen gonddal, esetleg van valami jó ötlete valakinek a megoldásra?
Köszönök minden segítséget!