>I have no other Ideas. Did these computers have some antivirus program installed with active FireWall that forbid the connections?

Just checked with the net guys, the answer to that one is 'Nope'. Thanks for the suggestions though.