Check names feature not resolving names in Contacts

I'm using Outlook 2k3 with a Exchange 2k server. For some reason when I
create a new email, select To:, type in the first or last name of a contact
in my address book, then select Check Names, Outlook cannot resolve any names.

I've tried changing the order of selection of where Outlook looks first
between the Contacts folder and the GAL already and that does not help.

Any ideas are appreciated.