You should check first if autocomplete is configured correctly in Outlook. This can be accomplished by going to the tools menu, select options, and then select the email options button on the preferences page. Once there, select the advanced email options button and on the next popup window consider all of the options. Make sure that automatic name checking and suggest names while completing To, CC, and BCC fields.
You mention the .NK2 file, and if it is not present then for some reason the clients file might have been deleted. If you have a backup of this file, there is an article for copying it at http://office.microsoft.com/en-us/assistance/HA011394511033.aspx
Hopefully this answers your question.