Did you install any Outlook plug-ins/3rd party add-ins? Sometimes extra add-ins can cause this to stop working.
HOWEVER, the file that stores this data is the *.nk2 file. I >>believe<< that the file is in %userprofile%/application data/Microsoft/Outlook. The file may be outlook.nk2, but if your Outlook profile is named something else, then the file will correspond with the outlook profile name. (ie. filename.nk2)
Try renaming this file to .old or some other extension. (I use my initials, that way if I do a cleanup on the file system it doesn't get clobbered with the rest of the *.old, *.bak, *.tmp etc...) In any case, renaming the file will allow you to revert back to it IF you need to do so. Anyway, try renaming the file and see if the Auto-Complete feature is corrected. It may not fix it, but I would try this 1st.
Good luck!
Al
P.S. This was probably the wrong forum.