You said "depsite the AD account being deleted".
Maybe the AD account is hidden from the Global Address List or just disabled?
I am not sure of a way that the mailbox still resides without an AD account.
If you had somehow deleted the AD account but the mailbox remains then you must re-associate these mailboxes with an AD account using the Exchange System Manager. Enterprise Vault requires that the mailbox be listed in the Global Address List in order to enable and archive the mailbox.
If the AD accounts are disabled or hidden from the Global Address List then you must unhide them in order to enable them for archiving.
Here is a TechNote that may assist you with your questions further:
To check if the Mailbox is hidden in the GAL.
http://support.veritas.com/docs/285147