Answer: 170

Solution:

A square $n^2$ ends in $256$ exactly when $1000 \mid n^2 - 256$ $= (n - 16)(n + 16).$ Modulo $8:$ $n^2 \equiv 0 \pmod 8$ forces $4 \mid n.$ Modulo $125:$ the factors $n \pm 16$ differ by $32,$ so $5$ divides at most one of them, and hence $125$ must divide a single factor: $n \equiv \pm 16 \pmod{125}.$ Because $16$ is a multiple of $4,$ the two conditions combine to $n \equiv \pm 16 \pmod{500}.$

So $\mathcal{S}$ consists of the numbers $(500m \pm 16)^2,$ whose square roots in increasing order are $16,$ $484,$ $516,$ $984,$ $1016, \ldots.$ The tenth smallest element of $\mathcal{S}$ is $(500 \cdot 5 - 16)^2 = 2484^2.$

The corresponding element of $\mathcal{T}$ is $\frac{2484^2 - 256}{1000} = \frac{2468 \cdot 2500}{1000} = 6170,$ whose remainder upon division by $1000$ is $170.$