No Outlook 2003/2007 clique em ferramentas - > enviar e receber - > baixar o catálogo de endereços
Isso resolverá o problema. Infelizmente você tem que fazer isso em cada cliente. O Outlook também fará uma sincronização peródica. No outlook 2010, clique na guia send receive e clique no catálogo de endereços de download.