As Eric Schneider asked, "Am I mistaken, or does the following (actually) elementary proof work?"
Theorem. Any integer which is a square modulo every prime is a square.
Lemma. For any odd prime $p$, any integer which is a square modulo $p$ is a square modulo every power of $p$.
Proof. Let $a$ be any square modulo $p$. Let $r$ be any integer $\geqslant 1$. Use induction on $r$. (I adopt this approach to avoid a bug, spotted by Ingix, in my earlier proof.) The result is true for $r=1$. Suppose, by the inductive hypothesis, that $a$ is a square modulo $p^{r-1}$. Then $a=x^2\mod p^{r-1}$ for some $x$.
Work modulo $p^r$. If $x=0$ then $a=0=0^2$ modulo $p^r$. Otherwise, for $0\leqslant k<p$, $(kp^{r-1}+x)^2=jp^{r-1}+a\mod p^r$ for some $0\leqslant j<p$.
Suppose two distinct $kp^{r-1}+x$ had the same square. Then
\begin{align*}
(kp^{r-1}+x)^2&=(lp^{r-1}+x)^2\mod p^r\tag{ with $k\ne l$}\\
(k^2-l^2)p^{2r-2}+2(k-l)p^{r-1}x&=0\mod p^r\\
2(k-l)p^{r-1}x&=0\mod p^r\tag{ as $r>1$}\\
2(k-l)x&=0\mod p
\end{align*}
$p$ is an odd prime and $x\ne 0\mod p$, so $p\nmid 2x$, so the last line is false.
Therefore, by the pigeonhole principle, the values of the $p$ distinct expressions $(kp^{r-1}+x)^2$ for $0\leqslant k<p$ are the values $jp^{r-1}+a$ for $0\leqslant j<p$ in some order. In particular, in one case $j=0$, so $a$ is a square modulo $p^r$.
Proof of theorem. Let $a$ be a square modulo every prime. Then, by Lemma 1, $a$ is a square modulo every odd prime-power. Then, by the Chinese remainder theorem, $a$ is a square modulo every odd integer. Then, by Eric Schneider's argument, with $n=2$, but applying it only to $p$ being an odd prime and not to $p=2$, for every odd prime $p$, $p^r\; ||\;a$ for an even number $r$.
Thus either $a=x^2$ or $a=2x^2$ for some integer $x$. Let $p$ be a prime where $p=\pm 3\mod 8$. Then, modulo $p$, $a$ is a quadratic residue modulo $p$ by supposition, but 2 is not a quadratic residue, so $2a$ is not a quadratic residue, so $2a$ is not a square in $\mathbb{Z}$. Thus for every integer $x$, $(2x)^2=4x^2\ne 2a$, so $2x^2\ne a$, so $a$ is a square, as required.
I see no elementary proof of this theorem, with no use of quadratic reciprocity (QR). I wonder if the above qualifies. Chan asked for a proof of this very result but that question was closed as a duplicate of a different question, viz the one where Eric Schneider's answer has been used above. There is Hagen von Eitzen's proof of a similar result, but that relies on QR. ArithmeticGeometer requested a proof without using QR, and the only answer is an advanced proof.
Best Answer
That $a$ is a square $\bmod p$ implies that $a$ is a square modulo every $p^k$ whenever $p$ is an odd prime not dividing a. If $p^{2m+1}\| a$ then it fails for $k>2m+1$.