In Outlook, select the File tab in the upper right corner; it should default to Info
Click on the large Account Settings button, and select Download address book
UNCHECK the box at the top that says to download changes since last send/receive
Click OK
This will take some time to complete since it will copy the entire address book from the Exchange server, but should resolve any "e-mail address you entered couldn't be found" issues where it is known to exist.