Stale User Deprovision and Undoing deprovision

Assuming you have a Search workflow step that is locating the inactive user objects to Deprovision, you could add an extra search condition that also looks at a DateTime Virtual Attribute (to be created or find an existing AD attribute to use) that is populated with a date upon an undo-Deprovision operation. You could create a DateTime Virtual Attribute for User objects and then have a Change Workflow populate this attribute with the date of the undo-Deprovision operation.

I was thinking of something similar to what Rich has suggested.

When the users are located and deprovisioned, mark a VA with the date and time.  Also, upon the undo-deprovision make sure you set the "must change password" flag.

Create a second Change workflow that reacts to the user changing their password by clearing the the date/time VA.

Finally, setup an Automation workflow that daily looks for stale dates in the VA and deprovisions the users with stale dates.

I was thinking something along those lines. However, a datetime attribute seems to be stored using a tick value. When creating operators with dates, I can only select strings in certain formats. How could I get around this limitation?

You don't HAVE to use a DateTime VA - you can use a directory string and manipulate string storage of the Date-Time if you find that easier.