$x^2-(p^4-16)y^2=p^2 \land x \mod (p^2-4) =2 \land x >0 \implies p | x,y$?
According to my calculation with PARI/GP , for the prime $$p=29$$ the smallest solution is $$x=511417665685259113593784321$$ $$y=608113496300320416961344$$ and we have $$x\equiv 1\mod 837$$