2003 Contact Problems

Ok so I have this weird problem that I'm not sure how to fix or where
to look.

I currently have Exchange 2003 and all Clients are running Outlook
2003. I create contacts and go into AD and create a contact ID for
the user, but being the fact that I that my company has such a high
turn over rate I am constantly changing the user association. The
association now is the phone and
everything
works fine with this but if I'm on a client machine and type the first
couple of letters of the name into the TO... line all the old
contacts are still in there even though the name association has
changed 1 year ago. How can I delete the old contacts from coming up
in on the client. The old contacts, when I click on properties have
this /o=xxxxxxxxx/ou=First Administrative Group/cn=Recipients/
cn=Charleyxxxxx and if I click on find contact it states that it
cannot find a contact with this email address. All help on this is
greatly appreciated.

Are these names cached in Exchange or in the clients Outlook?

Please help,

Jeff