A DESCRIPTION OF THE PROBLEM :
The behaviors of removeAll are different when an exception is thrown on c.contains(..) check.

"removeAll" of AbstractCollection and ArrayList removes the elements that were matched before the exception was thrown.
"removeAll" of ArrayDeque and ArrayBlockingQueue doesn't remove the elements because they use 2-phase logic, "Find all" and then "remove all".

I think it's also worth mentioning that "removeIf" behaves like ArrayDeque if the filter throws an exception.
I think there is no reason for these exception handling behaviors to be different.

Code Snippets.
ArrayList:
try {
            for (Object e; r < end; r++)
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;
        } catch (Throwable ex) {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            System.arraycopy(es, r, es, w, end - r);
            w += end - r;
            throw ex;
        } finally {

AbstractCollection:
public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

ArrayDeque:
for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
             ; i = 0, to = end, k -= capacity) {
            for (; i < to; i++)
                if (filter.test(elementAt(es, i)))
                    setBit(deathRow, i - k);
            if (to == end) break;
        }
        // a two-finger traversal, with hare i reading, tortoise w writing
        int w = beg;
        for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
             ; w = 0) { // w rejoins i on second leg
            // In this loop, i and w are on the same leg, with i > w
            for (; i < to; i++)
                if (isClear(deathRow, i - k))
                    es[w++] = es[i];
            if (to == end) break;
            // In this loop, w is on the first leg, i on the second
            for (i = 0, to = end, k -= capacity; i < to && w < capacity; i++)
                if (isClear(deathRow, i - k))
                    es[w++] = es[i];
            if (i >= to) {
                if (w == capacity) w = 0; // "corner" case
                break;
            }
        }