Eu tive esse problema antes em um site do cliente, pode ser totalmente não relacionado, mas vou postar minhas experiências aqui.
Meu primeiro porto de escala para diagnosticar isso foi abrir a perspectiva, deixar a janela de solicitações de credenciais aberta e, em seguida, ver para onde a solicitação de credenciais estava indo; O outlook possui uma ferramenta útil que mostra todas as conexões que está sendo feita. Para visualizá-lo, localize o ícone do outlook da área de notificação na barra de tarefas (os ícones à direita da tela pelo relógio, em vez daqueles à esquerda do menu Iniciar) e depois ctrl + clique com o botão direito do mouse para mostrar um pouco diferente menu de contexto, clique em Status da conexão.
Quando fiz isso, descobri que o Outlook estava tentando estabelecer uma conexão com pastas públicas em um servidor Exchange antigo que havia sido decommisionado e que isso estava acontecendo porque a pasta pública atual estava redirecionando para a antiga. Eu apaguei a pasta pública e recriá-lo e voila, sem mais solicitações de login.
É claro que existem cem razões pelas quais seus clientes do Outlook podem estar solicitando credenciais, mas eu recomendo verificar o status da conexão para ver onde ela está apontando. Descobri que, assim que inseri as credenciais, a conexão desapareceu no status da conexão, vale a pena tentar.