On the EV Server double check IIS:
1: On the Enterprise Vault Server open IIS Manager.
2: Navigate to the "EnterpriseVault" virtual directory and open the properties of this.
3: On the ASP.NET tab change the version from 1.1.4322 to 2.0.50727 or above.
4: From Command Prompt issue IISRESET command.
Regardless of what the Settings on the EV Server are do the following:
5: From client PC clear the Temporary Internet Files from Internet Explorer and test Vault Cache again.
If it is still slow post a client trace from the Users Outlook.
one last thing, have you seen this?
https://www-secure.symantec.com/connect/articles/simple-overview-vault-cache-how-it-works-and-troubleshooting