Why don't you just create a new Archive and Retrieval Service for the 'new' exchange server. As long as the mbx LegacyDN and display names are still the same then EV should just see these as having been 'moved' to a new server, sync them up and work.
Once you have created the new service and sync'ed the mailboxes you will want to make absolutely sure that you do not have duplicate entries in the exchangemailboxentry table in the EnterpriseVaultdirectory database.
It would also be nice to know how you went about restoring the mbx's. If you just remounted the information stores or exmerge'ed etc. EV relies heavily on its Filter message in the mailbox to get the vaultid's and then falls back on legacyDN, displayname if that is missing.