Pode ser várias coisas, mas duvido muito que seja o Office / Outlook que está em falta. Veja um pouco de reflexão e, se você tiver mais alguma informação em resposta a isso, edite sua pergunta original.
É o mesmo conjunto de usuários ou aleatoriamente diferentes? Os usuários têm algo em comum, como estão todos no mesmo banco de dados de caixa de correio? Você tem algum trabalho "pesado" em execução nesse banco de dados de caixa de correio (backup, software de arquivamento, verificação de vírus agendada, etc.)?
Você tem algum backup em execução no momento em que as mensagens estão acontecendo (é mais provável que isso aconteça em um backup completo, mas os logs de transações também também o fazem)?
Os usuários estão no modo de cache? Essa mensagem pode ser vista com frequência se os usuários tiverem uma caixa de correio grande e estiverem no modo "on-line".
Qual é a carga no servidor do Exchange? Se não conseguir acompanhar, você provavelmente verá essa mensagem enquanto tenta explorar todo o trabalho que precisa fazer.