Collection.removeAll() is specified to remove from this collection every element that is contained in the argument collection. This implies that the contains() semantics of the argument collection are used. However, CSLS.removeAll() iterates its argument and calls this.remove(), using the contains() semantics of this set instead of the argument collection.

(This is complicated by the performance heuristic in AbstractSet.removeAll, which is arguably broken. I've concluded that the contains() semantics of the argument collection must always be used. See JDK-6394757.)

The following jshell sessions illustrate the anomalous behavior (edited for brevity).

==========
jshell> List<String> removes = List.of("a", "b", "c", "d", "e", "f")
removes ==> [a, b, c, d, e, f]
jshell> Set<String> ts = new TreeSet<>(String.CASE_INSENSITIVE_ORDER)
jshell> ts.addAll(List.of("A", "b", "x"))
ts ==> [A, b, x]
jshell> ts.removeAll(removes)
ts ==> [A, x]
jshell> ts.addAll(List.of("A", "b", "x"))
jshell> ts.retainAll(removes)
ts ==> [b]
==========

The above shows that TreeSet uses the argument List's semantics of containership, namely case-sensitive equals(). Also note that the result of retainAll() is the complement of the result of removeAll(), which is expected. Now on to ConcurrentSkipListSet:

==========
jshell> Set<String> csls = new ConcurrentSkipListSet<>(String.CASE_INSENSITIVE_ORDER)
jshell> csls.addAll(List.of("A", "b", "x"))
csls ==> [A, b, x]
jshell> csls.removeAll(removes)
csls ==> [x] ***1***
jshell> csls.addAll(List.of("A", "b", "x"))
jshell> csls.retainAll(removes)
csls ==> [b] ***2***
==========

The result of csls.removeAll() at ***1*** indicates that the case-insensitive semantics of csls are used, instead of the case-sensitive semantics of List.

The result of csls.retainAll() at ***2*** is not a complement of the result of removeAll(), because retainAll() is inherited from AbstractSet and uses the contains() semantics of the argument.

CSLS should be fixed to iterate "this" and check contains() on its argument. It might be able to inherit from AbstractSet once JDK-6394757 is fixed.