Newly added Contacts not showing up when addressing an email

[david7777777777]

I've got Outlook 2000 talking to an Exchange 2003 box. Until last week we had been using a Linux-based POP3 mail server. Problem: when I go to create a new email and click the [To] button see my Contacts, Global Address List, etc. none of the new Contacts I've added show up in the list - only the Contacts that have been in my Contacts folder before the switch to Exchange are being listed. I've ensured that I am enbtering a valid email address in the email address field when I create these new Contacts. Any ideas why these new Contacts aren't showing up - even after re-starting Outlook? Thanks.