I accept informally your update on elementary vs. simple non elementary, but let us make it a bit more precise in order to go on. I guess everyone of us has at his disposal a favorite "tool kit" of concepts, theories, theorems, etc. which he uses to attack problems (solved or unsolved) and which depends on his formation. The point I want to stress is that every tool in such a kit is considered as already manufactured, ready for use without question, so that what you call a "simple non elementary" method just consists in a "ridiculously easy" (in your previous words) application of the tools contained in a kit labelled "non elementary". If you agree, then :
Concerning the diophantine equation $p = x^2+ny^2$, I think the solution explained in Cox's book belongs to the category "simple non elementary", the tool kit is just CFT, and all the more so when restricting to $n$ squarefree, $n$ not congruent to $3$ mod $4$ (this is just thm. 5.1 of the first chapter)
While we are at problems on sums of powers, here is a perhaps more convincing example. Sums of 2 squares belong to the elementary kit labelled "Fermat", sums of 4 squares to the (not so) elementary box called "Lagrange". And what about the Sylvester problem: when is a prime a sum of two rational cubes, $p=x^3 + y^3$ ? See e.g.
The answer is: (1) never for $p\equiv 2$ or $5$ mod $9$ (elementary kit "Fermat"); (2) always for $p\equiv4$, $7$ or $8$ mod $9$ (non elementary). In his course, Zagier gives 2 truly "gigantic" couples $(x, y)$ for $p= 382$ and $1789$ (the "french prime"), which tend to show that even a computer search for a negative answer would have been futile; (3) a necessary and sufficient (but not down to earth) criterion is available for $p\equiv 1$ mod $9$. The tool kit here could be labelled "Birch & Swinnerton-Dyer conjecture". More precisely, the Sylvester question is equivalent to whether the Mordell-Weil group $E_p (\mathbf Q)$ of the elliptic curve $E_p : x^3 + y^3 = p$ is non trivial, or else whether the rank $r_p$ of $E_p (\mathbf Q)$ is $>0$. According to BSD, this happens iff the $L$-function of $E_p$ vanishes at $s=1$. Although BSD is still a conjecture, enough partial results are known to show the properties (1) - (3) above. I stress that the BSD kit here contains tools related to the special value $L(E , 1)$ attached to an elliptic curve $E/\mathbf Q$, not to the specific Sylvester problem. Once the kit is granted, the case (2) is straightforward in your sense. But the case (3) is not simple, it is based on a theorem specific to the curve $E_p$ due to Villegas-Zagier.
Does this example cover all the aspects of your question about elementary/simple non elementary ?