In Version 6.0 SP1 and later, the entries that were not modified in the Exchangemailboxentry table had a 14 day tombstone period. There was a field that specified last updated or something like that.
The below technote is a poorly written tech solution. There seems to be a bit of confusion between EV and AD.
Clearing deleted mailboxes after synchronization
In 6.0, when the synchronization process checked a field in the ExchangeMailboxEntry (I do not remember which field and I do not have access to a 6.0 system but is was something like modified date) anyway, if an ExchangeMailboxEntry was not modified in the past 14 days (which means the mailbox does not exist in AD as far as EV was concerned) then the line in the ExchangeMailboxEntry would be deleted.
You may want to check with support to see if this is still the fact in 7.0 and 7.5. Please post back once you get and answer.
One more thing, Dtracing the provisioning and archive task then running a synchronization may help answer what is going on.
Jim S.