Deduplicated data objects are scrubbed by a executing a priority scrubbing task that scans the deduplicated data objects and applies a condition that enables priority data scrubbing based on the value of at least one attribute of the de-duplicated data objects. For example, a low priority task scrubs a deduplicated data object when a reference count of the deduplicated object reaches a threshold. A high priority task scrubs a deduplicated data object when a priority attribute indicates that the deduplicated data object is used by a critical source data object. A medium priority task scrubs a deduplicated data object when the access frequency of the deduplicated data object reaches a threshold. The condition may encode a scrubbing policy or heuristic, and may trigger further action in addition to scrubbing, such as triggering an update of the access rate.