Угу. Старая фича. Как-же я твой вопрос просмотрел
Можно еще одним способом, запустить Rebuild в Recipient Update Services на System Manager Exchange. Правда, ждать придется сутки. И еще, скажи юзверям, чтобы жали F9. По этой клавише, кроме получения почты, происходит "стягивание" адресной книги.