I've traced the problem down to a race condition - broker side - within SimpleAMQQueue.
The nub of the problem is the update of the atomic QueueContext._releasedEntry. There is a circumstance where _releasedEntry is overwritten prematurely and therefore the broker fails to resend the message to the client.
Here's how it happens:
In the cases where the tests fail, the thread (SubFlushRunner or QueueRunner) executing SimpleAMQQueue.deliverMessage() is yielded part way through the method. The thread has successfully sent the message to the client (MESSAGE_TRANSFER etc), but the JVM yields the thread before it reaches setLastSeen(). (SetLastSeen is responsible for advancing the lastSeen pointer, and resetting _releasedEntry if necessary).
Meanwhile, the client receives the message, calls JMS rollback, which causes MESSASE_RELEASE (etc) command to be sent to the broker, before it calls JMS receive(). The broker processes the MESSAGE_RELEASE by invoking SimpleAMQ.requeue() which in turn invokes updateSubRequeueEntry() to update _releaseEntry with the QueueEntry to be resent.
Now, the JVM wakes-up the thread (SubFlushRunner or QueueRunner) that was part way through processing SimpleAMQQueue .deliverMessage() for the initial send of the message. The setLastSeen() method is invoked, which **incorrectly** resets _releasedEntry to null because _releaseEntry now is the same as the entry being processed. The broker goes around the loop, calls getNextAvailableEntry which returns null because _releaseEntry has been prematurely cleared.
I've illustrated the success and failure cases as sequence diagrams (attached to this JIRA).