Pending messages with redelivered flag set to true stuck in queue

Issue

We have an scenario where the messages are not being delivered. When a consumer tries to get message, the broker returns that there are no messages in the queue and the redelivered flag of the message is set to true.

This is not expected, as the messages are clearly shown in the activemq console.

Restarting of AMQ broker does not help either. The new messages are being consummed but not the pending ones with redelivery flags set to true.

It seems to be simmilar to:
http://activemq.2283324.n4.nabble.com/ActiveMQ-not-delivering-messages-td4661471.html

Why this happened?
What about the workaround: queuePrefetch=0. Is this safe for any type of queue? What could be the performance impact to use the workaround?