Does http://support.microsoft.com/?kbid=287854 apply? Can you find the .nck file?
Also check the setting mentioned in http://www.infopackets.com/channels/en/windows/gazette/2003/20030630_microsoft_outlook_auto_complete_enable_or_disable.htm
(Suggest names while completing the To, Cc and Bcc fields).
Hope this helps.
One of my users has a problem. I'm sure you are all familar with the fact that outlook prefills email address as you are typing in the to field (if you've emailed at the address before). Well it is not doing so on my users computer so she either has to go to her address book or type the whole thing out. Any idea how to turn this feature on?