I’m only bumping this because I am experiencing this server connectivity blocked error now that I have started playing on PC again after a few months break:
I have tried every single Teredo Command prompt / device manager / registry edit / technique, restarts, installs, uninstalls.
I have no third party antivirus/firewall/networking software installed either - uninstalled avast premier and reset my windows 10 pro to barebones windows firewall with the default settings JUST like they said to do on the microsoft support.
I have even contacted microsoft support only to be told by them that I need to contact my local Internet service provider and ask them to make sure they are not blocking the required ports for the Teredo crap.
Command prompt is telling me that my Teredo connection is fine, my ipconfig is fine, my registry is fine, my services.msc settings for IP helper etc are all fine, every possible thing pre-required as they suggest is working and qualified, and my NAT type is OPEN instead of moderate/strict which is the best it can be, but it still says server connectivity is blocked.
My ISP then told me they are confident the issue is nothing to do with their hardware/network so I should contact microsoft again and tell them its their problem - now I contacted microsoft and they told me I need to phone microsoft network and outlook support on 1800-987-2301 for support on the networking issue, which is free in the USA but will be an expensive toll call from where I live.
I did contact my ISP three times and even bought a brand new modem and router and upgraded to the fastest Fibre connection available to eliminate the hardware/bandwidth possibility, and they confirmed that they dont block any ports but still I get server connectivity : Blocked.
I can still access the store and buy stuff and download shadows in shadowlab and all that stuff, but I cannot do any multiplayer matches/ranked mode or exhibition online vs…
it just searches forever and ever.
My last resort will be spending $100/hour to get a networking ITsupergeek to just come to my house and probably retry everything I already did and then call microsoft on a secret business/technician agent number and get some back door remote support that us laymen cant get on our own…but I hope I can solve it before throwing money at a problem that never existed when i forst bought the game for PC 
Would love to hear if anyone else is having the same issue -