One other option to try before raising a case (but only if all users use IE10 or higher) is to set the UseRestrictedSecurity web.config value to 0 for the Search virtual directory on the EV server. This VD is under the EnterpriseVault VD in the defa...
As JesusWept says, please raise a case as the root cause might vary in each instance. I have seen a variation of this where the Zone 4 (Restricted Sites) 1A10 registry value was not set to the default value of 3 (Block All Cookies), and strangely if...
As JW2 has mentioned it would be good to see a dtrace of StorageFileWatch, specifically to see if there is an (Exit) recorded for it:
{CVSDBAccessor::GetUnsecuredSavesetsCount} (Entry) PartitionIdentity = [3]
i.e there should be a dtrace entry a fe...