I wasn't able to find a single, popular pattern for doing this. But after poking around a bit in System.Messaging, I was able to leverage Message properties and MSMQ behavior in what I think was an appropriate way to get the job done with a minimum of moving parts.
Here is what I implemented. It turned out to be fairly simple and lightweight - not much code and easy to maintain:
I created an object called RetryLevel that has three properties:
int Order,
int NumberOfRetries,
TimeSpan Delay
The configuration of the receiver application now has a list of RetryLevel. So the new feature basically supports n-level retries.
Then I created an object called RetryInfo. This object has two properties:
int Attempts,
string SourceQueuePath
An instance of the RetryInfo object is serialized and stored in the Extension property of each Message that ends up being retried. This allows me to track the current retry state on the message itself, thus eliminating the need to maintain a separate retry metadata store and all the overhead of reconciling message Ids, keeping the data in sync, etc.
Finally, I added a wait queue path to the receiver's configuration. This queue is where messages will be dropped while they are in "timeout".
So now, when a message handler rejects a message, the receiver deserializes it's RetryInfo, if there is one, and looks at the number of (previous) Attempts to determine which of the configured RetryLevels it has reached.
The receiver then sets the the Message's TimeToBeRecieved (TTBR) property to DateTime.Now plus the Delay value of the appropriate RetryLevel. It then sets the AdministrativeQueue property to a Queue created from the RetryInfo's SourceQueuePath property and sets the Message's AcknowledgeType to AcknowledgeTypes.NegativeReceive. Finally, it puts the Message on the wait queue.
From here, MSMQ watches the Message's TTBR. When it times out, MSMQ puts the message back on the queue in its AdministrativeQueue property which is the queue the message originally came from. Should the message continue to be rejected by handlers, it just moves its way up the RetryLevels.
If a Message's Attempts is beyond that of all the NumberOfRetries on the configured RetryLevels, the message's TTBR property is set to TimeSpan.Zero, the UseDeadLetterQueue property is set to true and the message is put on the wait queue just like any other retry. This time, however, it times out immediately and MSMQ ships it to the wait queue's host's system dead letter queue (DLQ) where it can be dealt with manually.