After accidently deleting contact in Outlook 2010 Windows 7, No matter how many times re typing the contact in an email it won't show back in Auto Complete list
Have you tried adding the contact by using ADD CONTACT ? (sorry if that comes off a bit sarcastic)
https/support.office.com/en-us/article/Create-or-add-a-contact-20d3fd1f-fe1e-4e3d-9df7-3741ee393b50