Адреса в организации Exchange давно нет или изменен, а пользователи продолжают слать письма используя автоподстановку адреса в Outlook. Известная история? Мне тоже порядком надоела.
Думал, сам кеш хранится в реестре. Таки нет. Это файл в профиле пользователя *.NK2. Удаляем и забиваем! 
Если же есть желание подредактировать автозаполнение адресов, то можно воспользоваться программой NK2Edit.