[2021] Really weird multiplayer issue

Are you all on the Steam or a non-Steam version? or mixed?

If mixed, the Steam players need to opt into the crossplay branch in the Steam betas tab for this game.  

Then you might try all opting into that crossplay beta, as that uses Paradox MP services instead of Steam. If that helps you probably have some Steam ports blocked somewhere:

Required Ports for Steam - Steam Support

Article "Required Ports for Steam" support.steampowered.com