Hosting not works only joining session in Steam online multiplayer

I ran into a weird bug lately, and after searching answerhub and other forums it seems that it is quite a rare issue since I couldn’t find any mention of it.
I downloaded the Blueprint Multiplayer tutorial project

and built a version just to see how it works (no modifications whatsoever). It seems that some people can only Host a game, while others are able to Host and to Join as well. With some friends we were able to connect to each other a couple times, but with others it is impossible (if both of us can only Host a game). We always had the same result with a person, so if “User A” could only Host that was always the case, if “User B” could Host and Join as well, that worked like that all the time.
Every player had Steam running of course while testing, and we are not in regions where it should cause a problem (the testers were from the same country with the results above). Tried with 4.11 and 4.15. We have tried to open the ports UE4 using, but it didn’t work and even if it would it wouldn’t be a real solution since I couldn’t release a game if players need to open ports manually to play.
I assume that the tutorial project should work for everyone in both ways, so it really a mystery what could be the issue. It is really a pain, since a working Steam multiplayer is the only feature left to release a game I made.