Cannot play multiplayer at all

Yes it is a teredo issue. I’ve spent over a full day trying to fix it and no dice. Microsoft tech support has been completely useless. At this point I can no longer find any fixes for anything online that I haven’t tried yet. I just can’t get a teredo address.
No matter what I do I get
State: Offline
Error: Failed to resolve server name

At this point I’m pretty sure it’s impossible to fix this, so I’m just writing this in the vain hope that Irong Galaxy is somehow able to come up with some workaround.