You can try this utility, to either repair the file or move its data to a new file.

http://www.nirsoft.net/utils/outlook_nk2_edit.html

Or this one to dump the data out to a PST file and import it into Contacts where it should be.

http://www.nk2.info

Most importantly, impress upon your users that spending years to lovingly build up a temporary cache file that is subject to random corruption and data loss is NOT the way to go about it. That is what the Contacts part of Outlook is for. Anyone who loses important data because they were depending on the auto-complete cache to remember things for them deserves what they got.