Here is the situation:
Outlook 2003 opens and doesn't have any user information when typing a name in the To: field. When you send one email to one user, for the entirity of that session, the user you sent an email to will be suggested per the "Suggest names when completing" box (which is checked under the Tools|Options|Email Options|Advanced tab).
Once the user exits Outlook 2003 and reenters, the information is not retained. The send first situation can be recreated, but Outlook 2003 seems not to be saving the sender info between Outlook instances.
I found out where Outlook saves the file. Under Documents and Settings|*User*|Application Data|Microsoft|Outlook. When you go there and turn on all the appropriate view options (Tools|FolderOptions|View, Show the Hidden files and uncheck the Hide files) you don't see a NK2 file. A search for NK2 files yield no results. I created a dummy NK2 file hoping that Outlook would latch on to it. It exists in the appropriate place, but stays at 0KB and the problem persists.
I have not tried an uninstall and reinstall yet.
Has anyone else experienced this problem and/or know how to fix it? It looks like Outlook 2003 just isn't writing the To: addresses to the file or is incapable somehow of creating the file. All users have admin access to the computer.