Hmmm...maybe there's an entry that is screwing up the autocomplete list? You can try starting Outlook from a command line and use the "/cleanautocompletelist" switch.