@woozle 

UPnP is on and the DMZ is set to me. Unfortunately I dont have any other windows computers to test this on here at my home. I think I will call xbox support and see if they can fix the issue over there, because as you say, its not a problem with the router. But I will then tell you the results as it may still be an issue with the router. If I am smart then I would take this computer over to a friends house and then see if the teredo works there or not, but thats not a gaurentee that the router is at stake.

I hope to speak again soon.

P.S. I dont see the teredo notification in the TP-Link UPnP menu anymore. I only see two NAT-PMP 6881 tcp messages using port 6881 from my ip adress.

  @woozle 

I need to tell you that I managed to get the NAT type back open, I made this post on Xbox Forums and managed to get it back open. Now we can start worrying about the Server Connection being blocked. I have gone through the checklist on the windows report site again and that seems to not have worked.

I feel like we are once again on the right path to solving the issue.

  @Osanixian 

Ok, that's good to hear.

By the way, I think you should skip the section "7. Uninstall recent Windows updates" of the troubleshooting guide.

My computers have all the latest Windows updates installed and they have no connection problems.

  @woozle 

I have made a discovery, my antivirus has said that there was an inbound firewall rule for port 500 blocked, called by IKE and AuthIP IPsec Keying Module. I have since added the rule to the ESET firewall, which is dissimilar from the windows firewall, and the same rule is not there. There were also logs from multiple IP addresses blocked due to automatic blacklisting. The IP addresses blacklisted are currently: 31.7.60.114 ; 162.243.140.51 ; 185.164.72.21 ; 192.241.200.14 ; 194.165.16.78

I hope these insights help, goodnight and good luck.