I think "lock-free" is a misnomer. If you are using a test-and-set instruction, you have incurred all the performance cost of a lock. While much work has been done recently to improve the performance of instructions like CMPXCHG, you still need to treat them like a UDP broadcast message (avoid if possible).

One case I don't think he handles is if a user does a Lookup() for some value in a slot, then tries to delete that slot. In this case, the wrong value might be deleted if an InsertAt() happens in the meanwhile.