Your search request failed because an Enterprise Vault service was not available.
Wait and try again. If the problem persists, contact your Enterprise Vault administrator.

Sample Dtrace of the w3wp process from a Veritas internal lab:
104700 14:24:33.023 [27476] (w3wp) <30640> EV-H {SearchClient} Exception: Could not connect to net.tcp://evserver1.kvs.local:5114/enterprisevaultservice/search/. The connection attempt lasted for a time span of 00:00:21.0040789. TCP error code 10060: A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond 10.31.1.133:5114.
This happens when TCP/IP Port 5114 is blocked by a firewall.
Open TCP/IP Port 5114 between the EV servers.