I think there might have been some other condition. Otherwise, you could choose $ (x,y) = (12,11) $. Then $ x^2 - x + 3 = y^2 - y + 25 = 135 $

You're reading it wrong. It says that $y_{0}$ exists if and only if $x_{0}$ exists

The first one holds iff there is an $x_0$ s.t. $p|(2x_0+1)^2+11\ (*)$, while the second one holds iff there is an $y_0$ s.t. $p|(2y_0+1)^2+99\ (**)$. $(*)$ is equivalent to $-11$ being a quadratic residue $\pmod p$, while $(**)$ is equivalent to $-99=9\cdot(-11)$ being a quadratic residue, which is equivalent to $-11$ being a quadratic residue, and we're done.

The first assertion $\exists x\in\mathbb{Z}$ s.t. $p\mid(x^2-x+3)$ is equivalent to \begin{align*} \exists x,d_1\in\mathbb{Z}\text{ s.t. }x^2-x+3=(x-\tfrac{1}{2})^2+\tfrac{11}{4}=d_1p&\\ \iff(2x-1)^2=4d_1p-11&. \end{align*}We claim that the above is in turn equivalent to $-11$ being a QR $\pmod{p}$, i.e., $(\tfrac{-11}{p})=1$; indeed, necessity is apparent by taking the equation $\pmod{p}$. As for sufficiency, if $a,p-a$ are the "square roots" of $-11$, we can set $2x-1$ equal to whichever of $a,p-a$ is odd, such that $x$ is an integer. Then $(2x-1)^2+11=4(x^2-x+3)$ is divisible by $4p$, meaning $d_1=\tfrac{(2x-11)^2+11}{4p}$ is an integer and renders the above equation true; so we have the existence of the desired $x,d_1\in\mathbb{Z}$. Similarly, the second assertion $\exists y\in\mathbb{Z}$ s.t. $p\mid(y^2-y+3)$ is equivalent to \begin{align*} \exists y,d_2\in\mathbb{Z}\text{ s.t. }y^2-y+25=(y-\tfrac{1}{2})^2+\tfrac{99}{4}=d_2p&\\ \iff(2y-1)^2=4d_2p-99&, \end{align*}which we analogously determine is equivalent to having $(-\tfrac{99}{p})=1$. Hence, it remains to show that $(-\tfrac{11}{p})=1\iff(-\tfrac{99}{p})=1$, which is clear since $(-\tfrac{99}{p})=(\tfrac{9}{p})(\tfrac{-11}{p})=(\tfrac{-11}{p})$. Above, with $(\tfrac{-11}{p})$'s and $(\tfrac{9}{p})$'s thrown around, we implicitly require that $p>11$; fortunately, $p=2,3,5,7,11$ are easily verifiable by hand: $p=2$ renders both assertions false, because $x(x-1)$ and $y(y-1)$ are always even, and so $x^2-x+3$ and $y^2-y+25$ are always odd. $p=3$ renders both assertions true with $(x,y)=(0,2)$. $p=5$ renders both assertions true with $(x,y)=(2,0)$. $p=7$ renders both assertions false, because the residues of $n(n-1)\pmod{7}$ are $0,2,5,6$, so the residues of $x^2-x+3$ and $y^2-y+25$ are $3,5,1,2$ and $4,6,2,3$. $p=11$ renders both assertions true with $(x,y)=(6,6)$. All cases have been exhausted; the proof is complete. $\blacksquare$