I probably wrote my original comment a little too quickly. Yes, it's possible to write useful mostly lock-free data structures, but it's hard enough that I consider anyone claiming to have done so in a way that beats the equivalent locked structure (as you pointed out above) to be making an extraordinary claim that requires extraordinary evidence and serious consideration of the difficulty involved.
Nah. Anyone who actually understands this subject recognizes that a truly lock-free concurrent queue is probably one of the most difficult problems in all of Comp. Sci.
Even if you're using absolutes, its basically warranted because of the difficulty of the problem. No one will blame you for talking about how hard this problem is, even with a bit of hyperbole being used
The talk is 3.5 hours, about as long as you'd expect one to be for "writing a concurrent lockfree queue". Its an incredibly difficult topic, but I'm convinced that Pikus's implementation is actually correct.
Although, maybe there's a subtle bug somewhere. And Pikus is REALLLY stretching the definition of a queue to make his implementation work. (This queue may sometimes function like a stack, but that's okay because there's no way for the end programmer to figure it out without a global lock)
---------
EDIT: Oh, I guess you wouldn't consider it "truly lock free", because he has a global lock in the case of the rare situation of a full queue. He uses double-checked lock pattern for that case (and causes an expensive, but temporary, global lock on the data-structure) and basically says "This situation only happens once per hour, so its probably not bad".
So Pikus's implementation is "lock free mostly", but still falls back to a global spinlock in exceptionally rare corner cases.