You're missing something.
You don't understand how autocomplete works.
It has nothing to do with your Contacts. It uses a cache of names from
messages you have previously sent. Your cache is empty if you just turned
the option on.
Also, you did not post your Outlook version so we don't know for sure
whether your version supports the option. Which "option" did you turn on?