Searches can fail for the following reasons:
The Vault Service account does not have the right "Act As Part Of The Operating System" on every computer that is running Enterprise Vault software. This right must be separately set on every computer. If this is not set on an Indexing service computer, users are unable to search archives whose indexes are stored by that service.
The account performing the search does not have access to the archive. This could be simply because the user genuinely does not have access to a particular archive, or could suggest problems with the Directory service database.
Occasional failures to connect to an Indexing service, perhaps dependent on the user or computer, can be caused by DCOM security problems. Use dcomcnfg to verify that the Indexing service access permissions allow access to Everyone.
Check the security on the Index Location folders, and all files and subfolders within them. They must have an ACL giving full access to the local Administrators group. Unless your policies dictate otherwise, these files and folders should not be accessible by anyone else.