A varied least recently used (VLRU) caching technique is used to enable print data to be available at a cache of a client for printing, even after an agent performs a deletion of a hash value for the print data at a cache of the agent. The deletion of the print data (cached at the cache of the client) is postponed at the client device via the use of a waiting list, so that the cached print data can be printed at a physical printer of the client, in response to receiving a delayed print job from the agent that specifies the hash value as a result of a deduplication process performed by the agent.