Raze_Larian: I had to leave right after posting, so didn't see your reply, or try again.
No problem; still thanks a lot for your time, it was very helpful but I have to admit that I am at kind of a loss.
I was able to connect to you so apparently this part work; but I was unable to see your game in the lobby. (But maybe you just didn't set the game as "public")
On the other side neither you nor Lord_Kristof were able to connect to me, neither in direct nor via the lobby which would mean that there is an issue on my side but with my friend we had a totally different behavior. (I was failing immediately with a "Joining failed" error)
Raze, would you happen to know which ports are used by D:OS for multiplayer ?
Normally the process itself is allowed in my Windows firewall but I could try to explicitly open/redirect the ports in my router to see if it helps.