I believe there are some “Teredo-filters” or something you need to disable on fritzbox routers, found some posts like that while searching for a solution.
Click “Internet” in the FRITZ!Box user interface.
Click “Filters” in the “Internet” menu.
Click on the “Lists” tab.
Disable the option “Teredo filter enabled”. If the option is not displayed, enable the Advanced View first.
Click “Apply” to save the settings.
I have the exact same problem btw (Moderate NAT, Blocked server connection) and i’ve tried every fix there is but nothing seemed to have worked.
Well he did this aswell alrdy… I think toredo is not the problem, something else is blocking the connection.
We tried mutliple solutions but nothing workd to be honest… thats so sad, I mean u pay like 100 euros for this game, but nothing works wow.