AutoComplete not working

When I’m typing an address in the To field, Outlook doesn’t offer some of the addresses of my contacts.
How can I enable autocomplete for all my contacts?

Completing addresses when addressing an email works a bit different as Outlook doesn’t have an AutoComplete feature but has an AutoSuggest feature a Check Names feature instead.

Differences
The subtle difference between the two is that the AutoSuggest feature doesn’t have a direct relation to your Contacts folder or other address lists configured in your Address Book. Instead, AutoSuggest uses a cache which contains a list of addresses that you’ve previously used. For more about cleaning up your AutoSuggest cache list, see this previous tip.

Outlook also has another feature which is similar to AutoComplete; Check Names.
Check Names can work interactively and by default also works as a background process.

Check Names – Interactive
To use Check Names interactively, you type part of the name or address and then press the Check Names button on the Toolbar or Ribbon or press its keyboard shortcut (for most localized versions this is CTRL+K). This will search in your Address Book for that part of the name. If only a single address is resolved, it will directly show this in the To-field (or CC or BCC field). If multiple addresses are found, then it will prompt you with a dialog to select the correct address from.

Check Names – Background process 
When you only type part of a name or address and then switch to the message body, Check Names will perform a background search in your Address Book. If only a single address is resolved, it will autocomplete the address for you. If multiple addresses are found, it will underline the address with a red scribble line.
When you press the Send button while an address is not fully resolved, you’ll get prompted to select the correct address.

To turn of this background feature of Check Names go to;
Tools-> Options…-> E-mail Options…-> Advanced E-mail Options-> disable option: Automatic name checking