Based on the comments, it looks like this is not a question specific to Pell's equation, and that you just want to evaluate a single binomial with big inputs as quickly as possible.
If you check the equation directly using fast multiplication algorithms (e.g., Schönhage-Strassen), you can expect the calculation to require about $(\log z )\cdot (\log \log z)$ operations, where $z = \max \{ x, y, D \}$.
If you want a way to quickly find a negative answer, you can check relative sizes and leading digits, then try reduction modulo small integers. If you start with a random negative answer, you can expect it to be eliminated after at most a few divisions (i.e., about $\log z$ operations).
To find a positive answer using modular arithmetic, you can use the Chinese remainder theorem. To prove that the identity holds, it suffices to check it modulo $n$, for $n$ ranging over a collection of positive integers whose least common denominator is larger than $x^2$ and $Dy^2$. It is common to check modulo a large collection of small primes, and this will require about $\log z$ primes and $(\log z)^2$ operations. Another natural choice with a binary computer is Fermat numbers, of the form $2^{2^n}+1$, since the division-with-remainder can be optimized - this ends up looking a lot like direct calculation.
In summary, the advantage of checking modulo small primes is that it lets you quickly eliminate negative answers, and the disadvantage is that (if I'm not mistaken) it is roughly quadratically slower than direct calculation when you have a positive answer. You can choose your method depending on exactly what sort of calculation you plan to do.
There exist surprising counterexamples. Elsholtz and Dietmann found the following: If $p\equiv 7\pmod{8}$ is prime, then the equation $x^2+y^2+z^4=p^2$ has no non-trivial solution. You might argue that this equation is more of Waring then of Goldbach type, but remember that sums of two squares can be described multiplicatively, so it actually is pretty Goldbach like.
Best Answer
exp(exp(3)) is about 5e8 and testing the primes up to that is probably feasible with a few days of computer abuse. I tested up to 1e5 in 6 minutes with a trivial, single-threaded Haskell script (no more p's found). I don't see any particular reason to think there are no more p's though. It would surprise me if searching didn't turn up another p.