This problem is related to an known AD issue. Details of this problem, and the recommended workaround, were provided by a client who successfully fixed this problem in their environment using the information outlined at the following link.

MCSEworld Knowledge Base Tip:

Address List entries in Outlook are not updated even though I’ve made changes to users or groups in Active Directory. How can I fix this problem?
http://www.petri.co.il/gal_problems_and_oab_automatic_updates_in_outlook_2003.htm