FULL PRODUCT VERSION :
java version "1.8.0_112"
Java(TM) SE Runtime Environment (build 1.8.0_112-b15)
Java HotSpot(TM) 64-Bit Server VM (build 25.112-b15, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 6.1.7601]

A DESCRIPTION OF THE PROBLEM :
The TreeSet removeAll method seems to remove elements correctly with a custom comparator (String.CASE_INSENSITIVE_ORDER) when the number of elements in the Set is more than the number of elements provided as an argument to removeAll.

Consider the following snippet:

import java.util.*;

public class Test {
        public static void main(String[] args) {
                final Set<String> names = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
                names.addAll(Arrays.asList("jack", "john", "mark"));

                System.out.println("NAMES=" + names);

                names.removeAll(Arrays.asList("JACK"));
                System.out.println("After removing JACK=" + names);

                System.out.printf("JOHN %s in names%n", names.contains("JOHN") ? "exists" : "does not exist");
                names.removeAll(Arrays.asList("PAUL", "CINDY", "SARAH", "JOHN"));
                System.out.println("After removing JOHN=" + names);
        }
}

Why was JACK removed from the initial set : NAMES=[jack, john, mark] while in the next invocation john was NOT removed from the above TreeSet ?

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the following program:

import java.util.*;

public class Test {
        public static void main(String[] args) {
                final Set<String> names = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
                names.addAll(Arrays.asList("jack", "john", "mark"));

                System.out.println("NAMES=" + names);

                names.removeAll(Arrays.asList("JACK"));
                System.out.println("After removing JACK=" + names);

                System.out.printf("JOHN %s in names%n", names.contains("JOHN") ? "exists" : "does not exist");
                names.removeAll(Arrays.asList("PAUL", "CINDY", "SARAH", "JOHN"));
                System.out.println("After removing JOHN=" + names);
        }
}

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
NAMES=[jack, john, mark]
After removing JACK=[john, mark]
JOHN exists in names
After removing JOHN=[mark]
ACTUAL -
NAMES=[jack, john, mark]
After removing JACK=[john, mark]
JOHN exists in names
After removing JOHN=[john, mark]

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;

public class Test {
        public static void main(String[] args) {
                final Set<String> names = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
                names.addAll(Arrays.asList("jack", "john", "mark"));

                System.out.println("NAMES=" + names);

                names.removeAll(Arrays.asList("JACK"));
                System.out.println("After removing JACK=" + names);

                System.out.printf("JOHN %s in names%n", names.contains("JOHN") ? "exists" : "does not exist");
                names.removeAll(Arrays.asList("PAUL", "CINDY", "SARAH", "JOHN"));
                System.out.println("After removing JOHN=" + names);
        }
}
---------- END SOURCE ----------