Check that the Enterprise Vault registry entries are all set correctly on the newly-recovered servers.
The main registry entries are under the following key:
HKEY_LOCAL_MACHINE \SOFTWARE \KVS \Enterprise Vault
Additionally, you may have set registry entries under HKEY_CURRENT_USER when logged in as the Vault Site account. If so, restore these entries on each server too, under the following key:
HKEY_CURRENT_USER \Software \KVS \Enterprise Vault