Something went wrong. Contact your Enterprise Vault administrator. Try the operation after some time or contact your Enterprise Vault Administrator for more details.

Your search request failed. Wait and try again. If the problem persists, contact your Enterprise Vault administrator.

The issue occurs if the EV Search is opened against a URL which resolves to a network load balancer (NLB) and when it is not configured for session persistency. This causes the requests from the same client IP to be redirected to different EV Servers.
When an EV Search is first opened, it authenticates the user and sets the cookie on the client browser. If the subsequent request goes to any other EV Server, it cannot authenticate that user and hence the request fails.
A NetMon trace collected from the client machine shows responses like 401 - Unauthorized and 400 - Bad request while reproducing the issue:

At the same time, the EV Search works fine if opened directly from the EV Server URL.
The relevant team managing the NLB needs to configure the session persistency in order for the client machine to communicate with a specific EV server for the duration of the session. This will make sure all the calls are made to only one EV server with which user has authenticated initially.