Assume we are given two normally distributed random variables, $X_1$ and $X_2$, with $X_i \sim \mathcal N (0, \sigma_{x_i}^2)$, with correlation coefficient $\rho_x$. Assume further that we need to generate another two normally distributed random variables $Y_1$ and $Y_2$ with $Y_j \sim \mathcal N (0,\sigma_{y_j}^2)$, with correlation coefficient $\rho_y$ and cross correlation
$$\rho_{i,j} =\frac{\mathbb{E}\{X_i Y_j\}}{\sigma_{x_i} \sigma_{y_i}}$$
I.e., we need to generate $[Y_1, Y_2]$ taken into consideration the given $[X_1, X_2]$. I know how to generate all of them together $[X_1,X_2, Y_1, Y_2]$ using covariance matrix
$$M_{4\times4} = \begin{bmatrix} \sigma_{x_1}^2 &\rho_x \sigma_{x_1}\sigma_{x_2} &\rho_{1,1}\sigma_{x_1} \sigma_{y_1} &\rho_{1,2}\sigma_{x_1}\sigma_{y_2}\\ \rho_x \sigma_{x_1}\sigma_{x_2} &\sigma_{x_2}^2 &\rho_{2,1}\sigma_{x_2} \sigma_{y_1} & \rho_{2,2}\sigma_{x_2} \sigma_{y_2}\\ \rho_{1,1} \sigma_{x_1} \sigma_{y_1} & \rho_{1,2} \sigma_{x_2} \sigma_{y_1} & \sigma_{y_1}^2 & \rho_{y}\sigma_{y_1}\sigma_{y_2}\\ \rho_{1,2} \sigma_{x_1} \sigma_{y_2} & \rho_{2,2} \sigma_{x_2}\sigma_{y_2} & \rho_{y}\sigma_{y_1}\sigma_{y_2} & \sigma_{y_2}^2 \\ \end{bmatrix} = \begin{bmatrix} A_{2\times2} & B_{2\times2} \\ B^\top_{2\times2} & C_{2\times2} \\ \end{bmatrix} $$
I think we can generate $[Y_1, Y_2]$ by conditioning on $[X_1, X_2]$ and calculate the new conditional covariance, $\tilde{C} = \begin{bmatrix} C - B^\top A^{-1}B \end{bmatrix}$. Assuming that $A,B$ and $C$ are positive semidefinite (PSD), but not $M$, is it still possible to generate $[Y_1,Y_2]$?! or are we going to get always a non-PSD $\tilde{C}$.
You have a small typo: the conditional covariance is $C - B^\top A^{-1} B$.
If you take for granted that the formula for conditional covariance is correct, then you know it must be PSD simply because it is a covariance matrix. (Similarly, you know $A$ and $C$ must be PSD since they are covariance matrices for $(X_1, X_2)$ and $(Y_1, Y_2)$).
For general matrices that don't have any context as covariance matrices, you can refer to these results on the Schur complement.