I've specified wrong credentials, which Visual Studio then remembered.
How do I make NuGet/Visual Studio forget the wrong credentials?
As SayusiAndo guessed, the credentials were stored in Control Panel -> Credential Manager
. After removing of which everything works fine.
UPDATE: Two gotchas (as @Jurri mentioned in the comments):
There may be two credentials to delete (Windows and Generic). The generic one, in my case, had "VSCredentials_" prefix.
Restart VS.