We have $X_1=a+\epsilon_1$, $X_2=X_1+a+\epsilon_2$, the first two steps of a random walk with drift $a$, where $a$, $\epsilon_1$ and $\epsilon_2$ are independent RVs. I originally am interested in showing that $\mathbb{E}(X_2\mid X_1<x_1,X_2<x_2)$ is increasing in $x_1$ and $x_2$. It is not hard to show that $\mathbb{E}(X_2\mid X_2<x_2)$ is increasing in $x_2$, so one thing I can do is to write
$$\mathbb{E}(X_2\mid X_1<x_1,X_2<x_2)=\mathbb{E}(X_2\mid X_2-a-\epsilon_2<x_1,X_2<x_2)=$$ $$\mathbb{E}(X_2\mid X_2<\min\{x_2,x_1+a+\epsilon_2\})=\mathbb{E}(X_2\mid X_2<x^*(x_1,x_2))$$
for $x^*(x_1,x_2)=\min\{x_2,x_1+a+\epsilon_2\}$, a non decreasing function of $x_1$ and $x_2$, taking me to the case I know how to prove.
I am wondering, however, if in general, we can show that, when $Cov(X_1,X_2)>0$, $\mathbb{E}(X_2\mid X_1<x_1,X_2<x_2)$ is non-decreasing in $x_1$ and $x_2$.
Any thoughts on this? it seems intuitive, but haven't been able to show it.
Even in your original setting, it is false that $E[X_2 \mid X_1 < x_1, X_2 < x_2]$ is non-decreasing in both $x_1, x_2$.
First, here is the counter-example:
$a = 1$ (constant)
Bernoulli $\epsilon_1 \in \{0, 10\}$, with probability $1/2$ each.
Then $X_1 \in \{1, 11\}$ with probability $1/2$ each.
Bernoulli $\epsilon_2 \in \{0, 100\}$, with probability $1/2$ each.
Then $X_2 \in \{2, 12, 102, 112\}$ with probability $1/4$ each.
$E[X_2 \mid X_1 < 5, X_2 < 107] = {2 + 102 \over 2} = 52$
$E[X_2 \mid X_1 < 1000, X_2 < 107] = {2 + 12 + 102 \over 3} = 38.666... < 52$.
What is wrong with your "proof"? All your equations about expected values are correct. However, even for a given $(x_1, x_2) \in \mathbb{R}^2$, the term $x^*(x_1,x_2)=\min\{x_2,x_1+a+\epsilon_2\}$ is not just a real number. Instead it is a random variable, because $a$ and $\epsilon_2$ are both r.v.s. Therefore when you wrote $E[X_2 \mid X_2 < x^*(x_1,x_2)]$, the conditioning event
$$X_2 < x^*(x_1,x_2)$$
is a comparison between two random variables, $X_2$ and $x^*(x_1,x_2)$. Therefore, you cannot just invoke your result that $E[X_2 \mid X_2 < x_2]$ is non-decreasing in $x_2$, since that result only works when $x_2$ is a real number.
BTW, the two r.v.s $X_2$ and $x^*(x_1, x_2)$ are also dependent, since both their definitions involve $a$ and $\epsilon_2$.
Incidentally, the same counter-example also satisfies $Cov(X_1, X_2) =25 > 0$, thus answering No to your latter question also.