I thought about it again and I noticed something I also did before everything started working fine. I just installed gamespy.. Perhaps the standalone version of gamespy is important for online playing?
Would be interesting to know, whether all players, who don't have gamespy installed, are experiencing problems... I mean that would be less weird than my last solution, maybe ArmA uses some external gamespy stuff, although it shouldn't...