Спасибо за ссылки.

Да, архитектура x86. Я запускал на двухядерной машине.
Про TBB атомики почитаю.
Про Relacy Race Detector много раз слышал, и следующее что собирался сделать, воспользоваться им

Да, эта memory reclamation схема не очень хороша при очень частом вызове pop, в книжке тоже об этом сказано. Потом идут примеры с использованием hazard pointer-ов и счётчика ссылок. Однако программа падает довольно быстро. Дольше 5 секунд и не может продержаться, при одном потоке который пушит и двух попающих потоках. К сожалению не могу привести backtrace, сейчас на работе, приду домой скину.

Ещё я тут подумал что вот в этом месте

if (!--threads_in_pop_)
{
    if (to_be_deleted_.compare_exchange_strong(nodes_to_delete, 0))  
        delete_nodes(nodes_to_delete);

теоретически возможна ABA проблема. Между
if (!--threads_in_pop_)
и
if (to_be_deleted_.compare_exchange_strong(nodes_to_delete, 0))

некие другие потоки могут удалить текущий nodes_to_delete, потом в пуше он выделится заново, потом будет помещён вновь в to_be_deleted_. При этом кто-то может продолжать его использовать. Изначальный поток который уснул между этими двумя командами проснётся и благополучно удалит эту ноду хотя threads_in_pop_ != 0 и эта нода используется в другом потоке.

Для реализации такого сценария, нужно как минимум три потока вызывающих pop. А у меня падает с двумя потоками. Поскольку всё это скомпилено с -std=с++0x да ещё с 4.6.0 я не знаю на кого грешить. На книжку, на себя или на компилятор и сырую реализацию стандартной библиотеки