Outlook Contacts not syncing up right

Background:
Microsoft Exchange 2003 server
Outlook 2003
Blackberry Enterprise Server
User is coming in VIA VPN

PROBLEM
User creates a new contact in his local contact list
Then turns around and types a new message
Hits the TO button
And the user is not found in the contact list

However the contact is in his blackberry

Any thoughts