Outlook Autocomplete cache got you down after a migration (such as injecting useless X.400 addresses?).
You can clear the entire cache by deleting the *.NK2 file for your profile. In Windows XP or 2000, it’s in the hidden folder C:Documents and SettingsusernameApplication DataMicrosoftOutlook. Outlook will create a new NK2 the next time you use it.