One suggestion is to create a workflow that will start when a user object is deprovisioned.
Set the 'Target Properties' for property to:
'Apply Email Address Policy (edsva-MsExch-ApplyEmailAddressPolicy)' , Action=set, Value=False
'Address Book Policy (edsva-MsExch-AddressBookPolicyDN), Action=Clear
Refer to attachment called 'Remove Address Book Policy'