Could you provide a bit of motivation for this solution?

Okay, to be honest, I used a bit of computer help to construct the solution, and I am not sure how one could find it in a contest, but here we go: First of all, it is pretty clear that the answer should be YES, because it seems pretty much impossible to prove that such numbers do not exist (in particular, since small solutions certainly exist as $13^2=169, 14^2=196$). We thus set out to construct infinitely many solutions, by finding a parametric family. To begin with, by considering mod $9$ we need $n=9k+4$. This is helpful in looking for small solutions. We then get the obvious solution $n=13$ (with $169, 196$) and the slightly less obvious $n=157$ (with $24649$ and $24964$). Now my first attempt to construct a parametric family was as follows: If $n=100m+13$, then $n^2=10000m^2+2600m+169$ and $(n+1)^2=10000m^2+2800m+196$ and so it would suffice to find one single $t$ such that $13t$ and $14t$ have the same set of digits, since then we can put $m=5 \cdot10^kt$ for $k$ large. However, by checking the first few values, I did not find such a $t$ (note that $t$ must be a multiple of $9$, which again reduces the search). I am still not sure whether such a $t$ exists. However, instead of searching further, I tried to do the same thing with the solution $157$ instead of $13$. By the same ansatz, we just need to find $t$ with $157t$ and $158t$ having the same set of digits. Again, $t$ necessarily must be a multiple of $9$ and by searching we find the solution $t=9 \cdot 33$ where $157t=46629$ and $158t=46926$. Plugging this back, we get the solution in #3.

My answer is taking $297000......00157$, which also works.