Не стоит только когда есть работа.
Если блокировка удалась, поток выполняет свою работу. Если нет, возвращает Message в конец очереди и берёт следующий из начала. Остаётся только подобрать эффективный размер массива блокировок.
заводить промежуточную очередь ассоциированную с ID и складывать все сообщения с этим ID вынутые из основной очереди в неё.