auto complete in office outlook

HI,

In Office Outlook I renewed someones profile (control panel, mail, profiles). Now when they login and use outlook the auto complete function does not work for them. This isn't too bad when sending a mail internally but it means they have lost all the email addresses for customers (meaning he needs to look through old emails/ paper work to track an email).

Is there a solution to this problem?