Sampling from multivariate normal conditional on a negative minimum

Let $X\sim \mathcal{N}(\mu,\Sigma)$, where $\mu\in\mathbb{R}^n$ and $\Sigma\in\mathbb{R}^{n\times n}$.

How can I efficiently sample from $X | {\min{X}\le 0}$? (I.e. from the distribution of $X$ conditional on $\min{\{X_1,\dots,X_n\}}\le 0$.)

This seems harder than the usual problem of sampling from a truncated Normal, where Gibbs sampling works OK.

To see that Gibbs sampling is unlikely to perform well in my case, suppose that $\mu=[10,\dots,10]'$ and $\Sigma=I$, and suppose the sampler is initialized with $[0,10,\dots,10]'$. At the next step of the Gibbs sampler, the first coordinate must remain negative (as all others are positive), but with one coordinate negative, the conditional distributions of the other coordinates are just $\mathcal{N}(10,1)$, which is very unlikely to be negative. Thus the sampler will remain stuck with only the first coordinate negative.

1. Draw $i$ from $\{1,\dots,n\}$ with probability proportional to $\Pr(X_i\le 0)$.
2. Draw $x_i$ from the distribution of $X_i|X_i\le 0$.
3. Draw $x_1,\dots,x_{i-1},x_{i+1},\dots,x_n$ from the distribution of $X_1,\dots,X_{i-1},X_{i+1},\dots,X_n|X_i=x_i$.