Online set filling with redistributions
I can suggest two approaches:

Brute-force search

First try to find if there is a way to place the element, without redistributing any previously placed elements.

If not, try to find a way to place it, by redistributing exactly one previously placed element.  This can be done by enumerating all possibility for which element you redistribute and where you redistribute it to, to see if that leads to a valid placement.

If not, try to find a way to place it, by redistributing exactly two previously placed elements.  This involves enumerating all combinations of two previously placed elements to redistribute.

In general, if $n$ elements have been previously placed and $r$ redistributions are needed, this will involve enumerating ${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose r}$ possibilities, which is $O(n^r)$.  This might scale OK if you expect $r$ to be very small but becomes slow once $r$ is large.

SAT solver

To get a more scalable solution, I suggest you use a SAT solver.

There's a natural way to encode your problem as SAT.  Introduce boolean variables $x_{i,j}$, meaning that element $i$ gets placed in set $j$ after redistribution.  Each constraint is a clause (disjunction of some $x_{i,j}$'s).  Also, we can represent the requirement that at most $r$ redistributions be used as the sum of $\neg x_{i,j}$ over all pairs $(i,j)$ that correspond to an element that is currently placed in set $j$ (before redistribution).

Thus, you can represent the problem of finding a solution using at most $r$ redistributions as an instance of SAT, and solve it using an off-the-shelf SAT solver.  Use binary search over $r$ to find the minimal number of redistributions needed.

I expect that this will scale much better.