We had an issue with one PC that would not search Outlook 2013 Contacts. The only difference between this one PC and the others was that Office 2013 was installed using the Office 365 install vs the Office Professional 2013 Disk. After providing this information to TAC they came back with the following resolution.
HKEY_LOCAL_MACHINESOFTWAREWow6432NodeMicrosoftWindows Messaging SubsystemMAPIX (MAPIXshould be a String Reg key with a value of 1 HKEY_LOCAL_MACHINESOFTWAREWow6432NodeMicrosoftWindows Messaging Subsystem\MAPI (MAPI should also be a String Reg key with a value of 1
We had to add the MAPIX Reg Key and Search functionality started working.