The Active Directory Connector (ADC) service does not disable store management for mailboxes of deleted users.
In the ADC.wlog, it shows no deleted objects found.
"ADC Engine - Leaving HandleDeletedUsers. Found 0 deleted."
Enable Store Management is not automatically disabled for disabled Active Directory User Accounts.
The ADC Service account has no access to Deleted Objects container in Active Directory.
By default, only the System account and members of the Administrators group can view the contents of this container.
WORKAROUND 1
Add the Active Director Connector Service account to Domain Admins or BUILTIN\Administrators so that ADC service account can access the Deleted Objects container.
WORKAROUND 2
Grant Delegated access to the Active Directory Recycle bin
E.g
https://blogs.technet.microsoft.com/zarkatech/2011/06/14/delegation-of-active-directory-recycle-bin/
