É muito provável que eles tenham um dispositivo por aí que use uma senha antiga. Ocasionalmente, este dispositivo é ligado, dispara 10 (ou seja qual for o número) erros de login e bloqueia temporariamente a conta. Nesses momentos, o Outlook exibirá um prompt de login.
Você precisa procurar por todos os dispositivos que recebem e-mails ou tentam fazer login. Normalmente, este é um telefone ou tablet, mas pode ser outro cliente de e-mail em um laptop que foi completamente ignorado.
Quando você pergunta, eles podem até dizer: "Ah sim, eu fico com essa tela no meu laptop o tempo todo, mas eu não uso mais o email lá, então você não precisa consertar isso."