É melhor lidar apenas com a atualização do GAL / OAB e garantir que todos também atualizem o OAB também. Depois de atualizar o servidor do Exchange, você pode testar primeiro o OWA para garantir que as atualizações de OAB do cliente corrigirão o problema
Você pode seguir este artigo da Microsoft para fazer isso:
Como recriar rapidamente um catálogo de endereços offline do Exchange 2010
Siga para a parte do Outlook, mas antes de se preocupar em atualizar um cliente do Outlook, tente primeiro o Outlook Web Access e teste e verifique se você pode enviar para a nova caixa de correio. Em seguida, mexer com a atualização dos clientes do Outlook (ou apenas esperar mais de 24 horas, e eles vão buscá-lo automaticamente).
P.S. Pessoalmente, quando eu me deparei com isso no passado, eu não mexi com o endereço X.500. É um pouco de um PITA no início, porque depois que você fizer isso, novos e-mails funcionarão, mas os e-mails existentes que a caixa de correio original enviou se a resposta IF falhará. Este será um problema do helpdesk por alguns dias, explicando que as pessoas só precisarão criar um novo e-mail para a "nova" caixa de correio em vez de responder ao antigo. Após cerca de uma semana, praticamente se torna um problema inexistente.