Desative e ative novamente a verificação em duas etapas;
https://account.live.com/proofs/manage/
Se o erro persistir, tente conectar em outra rede ou na rede móvel e verifique se o problema ocorre.
Outra solução é conectar o Authenticator com a rede móvel e tentar fazer login nos outros dispositivos utilizando outro método de verificação.