AutoComplete, in Outlook, has a maximum number of contacts by default. This is either 1,000 or 2,000, depending on version, and can be changed by registry entry. One of the symptoms which shows up, is AutoComplete showing email addresses only for some entries, and not names.
The fix is here:
https://support.microsoft.com/en-us/kb/2199226
If you were using Exchange 2013 or later with Outlook 2013 or later, it is thought that AutoComplete may repair itself once the maximum has been sufficiently set. If automatic repair doesn’t occur, you’ll have to manually remove AutoComplete items and recreate.