DTrace the DirectoryService
Thats typically when the Admin Service has been started and the Directory Service is starting or has been stopped

Based on the frequency I would almost expect it to be a backup type script that has a delay between starting the admin and the Directory service

However it could be a long long start up of the DS, so you have to get a dtrace to see whether somethings holding up.

So maybe if you have a chance, stop all the services, dtrace admin and directory, start admin service and the directory service and see whether it starts up quickly or not, and if not, check the dtrace and see whats taking so long

In addition to what JW3 has suggested, does the EV Server have connection to the internet?

If not, try this:

1) Log onto the Enterprise Vault server as the vault service account.

2) Open Internet Explorer -> Tools -> Internet Options -> Advanced -> Scroll down  to Security and UNCHECK "Check for publisher's certificate revocation", Apply changes.

3) Start the Enterprise Vault services.

argh yeah, good catch tony! :)

Is this every time the machine is restarted?

Does the server have access to the internet?
Does the server have a ton of other programs added to it's startup?
Is there connectivity delays/issues between the EV server and the SQL server hosting the EV databases?
Is there significant load on the SQL server?

Does the certificate revocation actually resolve the problem? Most EV processes now have a config file that switches this off at the process level so no need for that IE change (in any case you have to remember to make that change when logged in as the VSA as it's effective on a per-user basis)