Eu não sei se isso está relacionado ou não ao seu problema, pois eu começaria corrigindo esses erros obviamente relacionados ao livro de endereço.
Para o primeiro: vá para as propriedades do Banco de Dados da Caixa de Correio, na guia "Configurações do Cliente" e configure o Catálogo de Endereços Offline que os usuários desse banco de dados devem usar (se você tiver apenas o padrão, selecione-o).
Para os outros: forçar uma reconstrução completa do Catálogo de Endereços Offline usando
Get-OfflineAddressBook | Update-OfflineAddressBook