My problem never went away completely. What I have learned so far, is that if I disable my firewall completely before starting Aoe2de, the game connects to multiplayer services properly and the problem doesn’t occur. After the game has connected and I’m in the main menu i can enable my firewall again no problem. So it seems there is something that my firewall is blocking at the moment Aoe2de launches. The strange thing is that according to the firewall it is not blocking anything even when it is active.