The thing is that the Show-In-Address-Book property is a multivalued property that is used by Exchange 2010 and higher to indicate the address books in which the user will appear. It is maintained by Exchange that is responsible for filling this property with GUIDs of address books based on address book policies.
I suggest that you wait for our next version that is to be released by the end of this month, in which there will be an option to hide an Exchange recipient from Exchange address lists. The new version will provide improved support for management of Exchange features, and hiding/unhiding from Exchange address lists will be done by means of native Exchange functionality. This means that all properties will be handled correctly.
As an option, if you have already deprovisioned some users and removed the Show-In-Address-Book property from their accounts, then, after re-provisioning a user, you need to run the following PowerShell command in the Exchange Management Shell:
Set-Mailbox -ApplyMandatoryProperties -Identity ReprovisionedUserName
where ReprovisionedUserName is the username of the user whose account you are re-provisioning.