“Fuzzy” Chinese Remainder Theorem NP-hard?
If you allow arbitrary modulus (so $m_i$ is not required to be prime), your problem is NP-hard.  In particular, it is NP-hard to determine whether there exists any valid solution, even without the upper bound $B$.

To prove this, we can reduce 3SAT to the problem.  Suppose we have a 3SAT formula $\varphi$ over variables $v_1,\dots,v_n$.  Let $p_1,\dots,p_n$ be the first $n$ primes.  Then we will associate one congruence per clause of $\varphi$.  In particular, the clause $v_i \lor v_j \lor v_k$ corresponds to the congruence

$$x \equiv a \pmod{p_i p_j p_k} \text{ where } a \in U$$

and $U=\{c_{001},c_{010},c_{011},\dots,c_{111}\}$ contains seven values, where $c_{def}$ is the unique constant such that $c_{def} \equiv d \pmod{p_i}$, $c_{def} \equiv e \pmod{p_j}$, and $c_{def} \equiv f \pmod{p_k}$.  Do the same for each other clause; e.g., for $v_i \lor v_j \lor \neg v_k$, the set $U$ has the seven values $U=\{c_{000}, c_{010}, c_{011}, c_{100}, c_{101}, c_{110}, c_{111}\}$, and so on.

In this way, we obtain a system of congruences with one congruence per clause of $\varphi$.  We don't need an upper bound on $x$ (you can use the trivial upper bound $x &lt; p_1 p_2 \cdots p_n$ if you like).  Then there exists a solution to this system of congruences iff the formula $\varphi$ is satisfiable. In particular, a satisfying assignment $(v_1,\dots,v_n)$ for $\varphi$ corresponds to a unique value for $x$ that satisfies all the congruences, namely, the value such that $x \equiv v_i \pmod{p_i}$ for all $i$.

This reduction does require the ability to choose moduluses that are not prime.  I don't know if the problem becomes any easier when every modulus is prime.