Encontrei o caminho sozinho.
É muito fácil de corrigir, mas é difícil descobrir. Estou compartilhando a solução se o problema ocorrer com outra pessoa.
Basicamente, o Outlook armazena contatos locais pessoais no arquivo de dados "Local" (ou seja, Outlook.pst), mas quando me conectei ao Exchange ele decidiu usar o instantâneo local do Exchange como padrão arquivo de dados .
O ActiveSync / WMDC procura a pasta padrão, então você precisa restaurá-la para a pasta local.
Vá para Arquivo \ Configurações da conta, arquivos de dados e escolha o arquivo .pst correto como arquivo padrão.
Em seguida, reinicie o Outlook.