Похоже на типичный случай с ABA – твои узлы постоянно переставляются, а CAS видит одно и то же значение дважды. Попробуй пометить указатели счетчиком или используй схему hazard-pointers, чтобы обнаруживать переиспользованные узлы. Еще раз проверь, что каждая операция чтения использует acquire-ordering, а каждая запись – release-ordering; отсутствие барьера может зависнуть всю очередь. Если логика все еще кажется хлипкой, временно перейди на проверенный lock-free кольцевой буфер, а потом, когда разберешься с порядком, верни свою очередь. И не забудь добавить небольшое экспоненциальное задержку при неудачных CAS; это не даст потокам постоянно бить в одно и то же место.