I've been with this problem for quite a few days and still I haven't solve it yet.
The user was unable to search contacts in Lync 2013 client even though MAPI and EWS Status are OK.
We are using Outlook 2007 and Lync 2013. I already tried installing SP3 for Office 2007.
Please help.
Let me know if you need further information.
Thanks in advance.

Hi,

Would you please elaborate your issue please? Such as where the issue happen (couldn't search Lync contacts on Lync client, or on Outlook),

If the issue happen on Lync client (on Lync client, users fail to search other Lync users), then run Lync Server Management Shell: Update-CsAddressBook to trigger the Lync Server to synchronize current Active Directory information in the SQL database into the downloadable client and device address book files.

Then on Lync client delete Lync user profile and then test again:

%UserProfile%\AppData\Local\Microsoft\Office\15.0\Lync

If the issue is which the Lync contact couldn't appear on Outlook 2007, make sure that on Lync client, Option--Personal--Personal Information Manager, the option "Microsoft Exchange or Microsoft Outlook" choose.

Best Regards