Failure to launch co-op missions

Hi folks,

I'm at a bit of a loss with coop and would appreciate help, if possible.

For some reason, any time I try to launch a coop game, the mission fails to launch. I get the "Creating game" popup, however the mission itself never actually launches. After a while I get the "Failed to launch" message in my chat window.
It does not matter what mission it is, neither whether I am the party leader or not.

Solo missions all work perfectly well, I did also try to test whether PVP is possible and I did manage to play a match with someone.

All my settings should be in order, Multiplayer settings are set for WAN and Nat punchthrough, my local firewall has exceptions for all aoeo executive files and I even tried to completely turn off the routes firewall, ports are open as well (1000-1005 UDP).

I don't know what else to try and I'm not willing to go with some Hamachi-like ordeal that we used to do in the old days. Don't believe it should be necessary and the issue is somewhere else, just can't seem to be able to find it.

Please let me know if you need any more details to figure out what could be wrong or if you already have suggestions.