Need solution to Exchange Mailbox move situation

I work in Desktop support for a large corporation. Recently our Exchange admin moved some user mailboxes from one server to another. Now we have a situation...
Users who have emailed other users previously have that email address cached in Outlook..you know where they start to type a name, and Outlook completes the address... Apparently Outlook is completing the email addresses and resolving them to the old email server. And now our Exchange admin is telling us the only solution to this is to re-profile each user locally on their PCs, but that's like 2000+. There has to be another way, and I am asking you in the community for help if you have the answer.
Thanks!