I faced the very same problem below in many exchange deployments I have done.
We have a single Exchange 2010 server handling client access, hip transport and mailbox roles.
When I setup an account in an outlook 2010, the address list of all current exchange users comes from the server and stays in the client side.
The problem is, when we add, modify or remove an email address in the server side, all users who are using Outlook don't get their address list updated.
1. How to solve this permanently.
2. How to force an update for the address list for a particular user without removing and re-setting his exchange account in outlook.