We propose C-NORTA, an exact algorithm to generate random variates from the tail of a bivariate NORTA random vector. (A NORTA random vector is specified by a pair of marginals and a rank or product-moment correlation, and it is sampled using the popular NORmal-To-Anything procedure.) We first demonstrate that a rejection-based adaptation of NORTA on such constrained random vector generation problems may often be fundamentally intractable. We then develop the C-NORTA algorithm, relying on strategic conditioning of the NORTA vector, followed by efficient approximation and acceptance/rejection steps. We show that, in a certain precise asymptotic sense, the sampling efficiency of C-NORTA is exponentially larger than what is achievable through a naive application of NORTA. Furthermore, for at least a certain class of problems, we show that the acceptance probability within C-NORTA decays only linearly with respect to a defined rarity parameter. The corresponding decay rate achievable through a naive adaptation of NORTA is exponential. We provide directives for efficient implementation.