This has been driving me nuts for years. The solution, as it turns out, is ridiculously simple: at the top right of Visual Studio, go to your signed in account => Account Settings ...
On the dialog that pops up, sign out of all accounts and close the window.
While signed out, close and restart Visual Studio.
Sign in again with your accounts. You should be good to go.
Apparently signing out and closing Visual Studio is the only way to truly clear its credential caches. Fuck.