that's why you should always use a unique identifier instead.
Since we take the user's "objectGUID" attribute as a unique identifier we don't have any issue with name changes anymore (see SID vs. GUID) as long as you don't create completely new objects for the same user:
When a new domain user or group account is created, Active Directory stores the account's SID in the Object-SID (objectSID) property of a User or Group object. It also assigns the new object a globally unique identifier (GUID), which is a 128-bit value that is unique not only in the enterprise but also across the world. GUIDs are assigned to every object created by Active Directory, not just User and Group objects. Each object's GUID is stored in its Object-GUID (objectGUID) property.
Active Directory uses GUIDs internally to identify objects. For example, the GUID is one of an object's properties that is published in the global catalog. Searching the global catalog for a User object's GUID will yield results if the user has an account somewhere in the enterprise. In fact, searching for any object by Object-GUID might be the most reliable way of finding the object you want to find. The values of other object properties can change, but the Object-GUID never changes. When an object is assigned a GUID, it keeps that value for life.
Don't forget to add some business rules for this case (e.g. Update Windows-Integrated-Login to match the new loginid etc.) and you won't have any issues anymore. :-)
Thanks for your reply, Florian. Unfortunately it's not really a solution to my problem. I'm not in a position to change the way we run ID provisioning at my institution, and I'm well aware of the fact that it's sub-optimal. Does anyone have an idea of how I can work around the issue? Alternately, is there a way I'm not thinking of that I can use to "expire" accounts based only on their non-presence in Active Directory?