TeamCity has no issues - it's actually AZURE that has a problem.
For proof, try doing this in your server, where TC is installed.
(command line, of course)
C:\git\bin\git.exe clone https://github.com/libgit2/libgit2.git
and this should not work most of the time.
So AZURE has a networking bug and they know about it and are trying to resolve the issue.
This info was provided via GitHub after they worked with Azure to figure out what was going on.
Conclusion
You have to use SSH KEYS as a current workaround.