This is because you use a Status field for messages and leave unreceiveable messages in the queue. Retaining messages (keeping them after process, with a different status) leads to queue bloat, contention, poor plan choices and general slow processing.

Follow Using tables as Queues and do distructive message processing:

DELETE TOP (1) 
FROM [queue].[Messages] m WITH (ROWLOCK, READPAST)
OUTPUT deleted.*;

Also drop all indexes on the queue. The linked article has details how to achieve fancier behavior like FIFO or Pending.

Use queues only for events, not for state.

This is because you use a Status field for messages and leave unreceiveable messages in the queue. Retaining messages (keeping them after process, with a different status) leads to queue bloat, contention, poor plan choices and general slow processing.

Follow Using tables as Queues and do destructive message processing:

DELETE TOP (1) 
FROM [queue].[Messages] m WITH (ROWLOCK, READPAST)
OUTPUT deleted.*;

Also drop all indexes on the queue. The linked article has details how to achieve fancier behavior like FIFO or Pending.

Use queues only for events, not for state.