A nevrací se buď přímo ten set nebo třeba jen iterátor někam mimo tu třídu, takže se k němu už přistupuje mimo synchronized? (teď nemyslím nutně ten testovací kód).
Jinak přelinkování objektů v HashSet/Map se může rozbít samo o sobě, pokud tam dělají dva thready něco zároveň, počítadla (včetně isEmpty()) to samozřejmě ještě zhorší.
A ano, ve chvíli, kdy se interní struktura rozbije jednou, tak se dohromady může dát už jenom stejnou (opačnou) náhodou (teď "mírně" zjednodušuju). Takže zůstane nejspíš rozbitá napořád.
Zkusil bych buď ConcurrentHashSet (tedy spíš zabalený Map) nebo Collections.synchronizedSet() ... Nebo spíš je otázka, proč něco, co se nazývá queue, je jenom Set a nikoliv (Blocking)Queue...