I’ve tried everything, even this suggested by Microsoft: Xbox Support
Teredo isn’t in my Device Manager, even when I enable ‘show hidden’ and disable Teredo in CMD.
However, on my XBOX One I can play online without issues so it’s most likely not a router issue.
I had the same issue with Teredo, fixed it by opening PowerShell as admin (Command Prompt should work too) and typing “netsh interface teredo set state servername=win10.ipv6.microsoft.com” to fix the incorrect server address, followed by “netsh interface teredo set state type=client” to enable the service.