Outlook 2003 Autocomplete contacts

Can anyone help????

I have user who has recently upgrade from Outlook 2000 to 2003.

The user has several hundreads of contacts, which were transferred.

For some reason now, any new contacts the user adds are not picked up when
attempting to use the Ctrl+k function? Auto complete does however work
once an email has been sent to the new user! Is this by design? Or should
it work once the contact has been setup?

We are currently working on an Exchange 5.5 server.