Depois de ativar o log de depuração, conforme a sugestão de joeqwerty, descobri que as contas que não conseguiam se conectar usando o IMAP estavam lançando o erro 0x80040920. Um pouco de Googling localizado neste artigo da base de conhecimento da Microsoft .
Embora o artigo fale sobre o POP3, ele também é relevante para o IMAP. Especificamente, o alias de email definido nas contas afetadas não correspondia ao ID de logon. A solução foi simplesmente alterar o alias para corresponder ao ID de logon. Eu também tentei excluir o alias, mas isso não funcionou.