Embodiments of the present invention are directed to facilitating efficient message queueing. In particular, embodiments herein describe, among other things, a redelivery monitor used to monitor when to redeliver messages, or tasks, for reprocessing based on expiration of a redelivery deadline. In this regard, markers indicating processing states for tasks being processed are read by the redelivery monitor. When the processing state indicates that processing is ongoing, the redelivery deadline is extended such that a message or task is not redelivered for processing while the message or task is being processed.