I also contacted Stardock Support about this. I gave them a detailed description, as also shown here in the thread. At first they asked for even more information (Router firmware, type of DSL, tracert). Then they told me, that the issue is with my ISP and tht ADSL has issues with the P2P connection setup and that they are in the process of setting up a solution.
Which is fine, but I asked for more technical details, since I am using an ADSL connection in my home town too and everything works great there. I also explained that I never get to the part of connecting to other games. As far as I understand it, the NAT facilitator would provide me with the connection details of the other players in the game, but the game is never able to connect to the NAT facilitator. I also told them, that the game is supposed to connect to the NAT facilitator via port 6000 UDP, yet it never happens.
Another support guy suggested that I "could try the ImpulseReactorOptions application located in the Demigod\bin directory. This will allow you to specify the port range used to connect to the NAT facilitator, and forward ports accordingly." But I already did that of course and these are just the ports (or the port) on which other players will connect to me and not the port on which the NAT facilitator connects to me. Besides, I am unable to connect to the NAT facilitator, not the other way around.
Maybe the upcoming Proxy and updates will fix this somehow. I sure hope so.