Outlook Address mixup

Hi,

One of our users Lennard is experiencing an issue with there outlook. He is trying to send a mail to Bob. Bob recently switched mail addresses with Carol. When he sends a mail to Bob by typing in the mail address "work"@gmail.com it sends to Carol but if he sends the mail by searching Bob's name it sends to Bob but the mail address is still "work"@gmail.com. I'm thinking it is an issue with his Autocomplete or address book. Has anyone come across this before. If so how would I go about correcting the issue.