Limits on lock-free collections? David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way.

This statement isn't very precise, but let me try to rephrase it in a slightly more formal way: For every collection type C, there exists a lock-free collection type CLF that offers the same set of operations, and where each operation on CLF has the same big-O complexity as the corresponding operation on C.

I don't expect a transformation, by the way.
Since I was myself somewhat confused, I begin by clarifying a few concepts in the question.

Collection. I see no reason to spend time rigorously defining what "collection" means when we can simply ask what happens for data structures in general. A data structure occupies a piece of memory and has some operations that may access that memory and that may be invoked by users. These users may be distinct processors or just different threads, it does not concern us. All that matters is that they may execute operations in parallel.

Lock-free. Herlihy and Boss say that a data structure is lock-free when a crashing user does not prevent further uses of the data structure. For example, imagine one pours water on a processor that is in the midst of inserting a node in a sorted set. Well, if other processors try later to insert into that sorted set, they should succeed. (Edit: According to this definition, it is the case that if a data structure uses locks then it is not lock-free, but it is not the case that if a data structure does not use locks then it is lock-free.)

With these definition, I think Herlihy and Boss basically say that the answer is to turn critical regions into transactions.

But, you may ask, does this have the same complexity? I'm not sure the question makes sense. Consider push(x) { lock(); stack[size++] = x; unlock(); }. Is this a constant time operation? If you ignore the locking operation and hence other users then you can answer YES. If you do not wish to ignore other users, then there really is no way to say whether push will run in constant time. If you go one level up and see how the stack is used by some particular algorithm, then you might be able to say that push will always take constant time (measured now in terms of whatever happens to be the input of your parallel algorithm). But that really is a property of your algorithm, so it doesn't make sense to say that push is a constant time operation.

In summary, if you ignore how much a user executing an operation waits for other users, then using transactions instead of critical regions answers your question affirmatively. If you don't ignore the waiting time, then you need to look at how the data structure is used.