I forgot to post about this at the time. Cliff Click gave a talk about his lock-free hashtable at Google; it is definitely worth a peek. Available here.
There is a very funny thread on the concurrency-interest mailing list this week about "lock-free mania". Apparently, software engineers are going to start choosing "trendy" lock-free data structures for no valid reason, resulting in lots of fragile code. In related news, recursion, memoization and every data structure more complicated than a hash table just started laughing their arses off. B+ Trees were quoted as saying, "I can't count the number of times some database-implementing hack has thrown together a cheap and poorly tested implementation of me because he thinks it is 'trendy' to put together an indexing mechanism. Oh, wait. Zero is a number. Never mind!"
In all seriousness, I have actually stopped someone from using a lock-free algorithm where a lock would have been more readable, and had the same performance impact. So, as with every other programming technique on the planet, you have to be careful about where you use it.
Personally, I see the complexity of lock-free algorithms as a hack that just needs to hold us over until hardware atomicity is supported for more than 1 word at a time. I actually asked Cliff about this in the talk, because he controls his hardware (I start laughing, he stares at me for a bit, and then I ask that question, which was not the question I was imagining.) He only did it in the way he did because he wanted his hash table to be useful for other Java implementations. That's community spirit for you!