I've had similar problems with EV. But the problem wasn't within EV itself. EV is using browser settings for the Archive Explorer and the Search Vault function, so perhaps this could be that you have either a mismatch within the settings in Internet Explorer (Intranet pages, security settings - check the advanced settings within the policy that you may apply for the specific users) or it can be a proxy problem where the proxy mistranslate the connection, perhaps an issue with the domain or fqdn ?
I would check the following:
Security Settings within the policy
The url specified in the general settings in EV (right click on the EV directory and pick propperties)
The DNS aliases
The proxy settings (do the proxy server allow the various connections)
Good luck =)