We prove the existence and uniqueness of viscosity solutions to quasi-variational inequalities (QVIs) with both upper and lower obstacles. In contrast to most previous works, we allow all involved coefficients to depend on the state variable and do not assume any type of monotonicity. It is well known that double obstacle QVIs are related to zero-sum games of impulse control, and our existence result is derived by considering a sequence of such games. Full generality is obtained by allowing one player in the game to randomize their control. A by-product of our result is that the corresponding zero-sum game has a value, which is a direct consequence of viscosity comparison. Utilizing recent results for backward stochastic differential equations (BSDEs), we find that the unique viscosity solution to our QVI is related to optimal stopping of BSDEs with constrained jumps and, in particular, to the corresponding non-linear Snell envelope. This gives a new probabilistic representation for double obstacle QVIs. It should be noted that we consider the min-max version (or equivalently the max-min version); however, the conditions under which solutions to the min-max and max-min versions coincide remain unknown and is a topic left for future work.