Recently we've had a handful of users who can no longer search Contacts in Outlook 2010. Some have several other users' Shared Contacts. They can browse the data fine, but searching provides no results. We've tried Rebuilding the Index and it worked for a few days and then stopped working again.
We are on Exchange 2010.