Тут есть несколько проблемных мест:
1. Кэш самого Exchange — но он достаточно быстро загружает новую информацию из AD
2. Кэш адресов в Outlook — лечится запуском Outlook с ключом /cleanautocompletecache Можно делать запуск с помощью GPO/GPP.
3. Наличие адресов в локальных контактах в Outlook — централизованно никак не лечится.
4. OAB перегенерируется ночью (это можно делать чаще автоматически или ручками), а на клиенты загружается автоматически в течение суток (это время не настраивается, но пользователь может загрузить OAB ручками)