Wish I had some better answers for you, but I don't. Seems strange that it works sometimes and not others. The only thing I noticed is that in both examples you've posted the "delay" is very long. Are these new messages that are failing, or are you still trying to process the deferred queue? Have you dug any deeper into the logs to see if there are more messages associated with these failures?