Let $\mathcal{S}$ be the set of all perfect squares whose rightmost three digits in base $10$ are $256$. Let $\mathcal{T}$ be the set of all numbers of the form $\frac{x-256}{1000}$, where $x$ is in $\mathcal{S}$. In other words, $\mathcal{T}$ is the set of numbers when the last three digits of each number in $\mathcal{S}$ are truncated. Find the remainder when the tenth smallest element of $\mathcal{T}$ is divided by $1000$.
Firstly, we note that if $x^2$ ends with $256$, then $(x+1000)^2$ must end with $256$ too because $(x+1000)^2\equiv x^2\pmod{1000}$. Hence, we just need to focus on numbers less than $1000$.
Next, $x^2$ ends with $256$ is equivalent to say $x^2-256=1000\cdot k$ where $k$ is an integer. This implies $(x+16)(x-16)$ is a multiple of $10000=2^3\times 5^3$.
Now because $x+16 \not\equiv x-16\pmod{5}$, therefore $(x+16)$ and $(x-16)$ cannot both be multiples of $5$. Hence, one of them must be a multiple of $5^3=125$.
Meanwhile, because $x+16\equiv x-16\pmod{4}$, therefore both of them must be multiples of $4$. Otherwise, if neither of them is a multiple of $4$, then $(x+16)(x-16)$ cannot be a multiple of $2^3=8$.
Combining both facts means one of $(x+16)$ and $(x-16)$ is a multiple of $125\times 4=500$ or $x=500n\pm 16$. Now, it is just a matter to check $16$, $(500 - 16)$, $(500+16)$, and $(1000-16)$. Squares of all of them end with $256$.
Therefore, the $10^{th}$ smallest qualifying number is $(2000+500-16)=2484$. And the desired answer is $$\frac{2484^2 - 256}{1000}\equiv\boxed{170}\pmod{1000}$$