Meu palpite é que seus usuários estão operando no modo em cache quando se conectam ao Exchange. Se for esse o caso, eles provavelmente estão baixando o catálogo de endereços offline. Isso é gerado em um agendamento e depois atualizado pelos clientes regularmente.
Você pode alterar o cronograma padrão para atender às suas necessidades de negócios (a frequência das alterações, o tamanho da lista de endereços, etc.).
Um bom artigo que explica como trabalhar com os blocos de endereços off-line é encontrado no link .
É claro que pode ser que meu palpite esteja errado e não é isso que você está experimentando, mas sem mais informações, isso pelo menos lhe dá uma resposta possível.