4. Mary found that when a certain three-digit number is squared, the last three digits of the product are the same as the original three-digit number. What is the sum of all different three-digit numbers that satisfy this property?
4. Let the three-digit number be $\overline{a b c}$, then
$$
\overline{a b c}^{2}=1000 k+\overline{a b c} \text {, }
$$

i.e., $\overline{a b c}(\overline{a b c}-1)=2^{3} \times 5^{3} k$.
Since $(\overline{a b c}, \overline{a b c}-1)=1$, therefore,
$2^{3} \mid \overline{a b c}$, and $5^{3} \mid(\overline{a b c}-1)$,

or $2^{3} \mid (\overline{a b c}-1)$, and $5^{3} \mid \overline{a b c}$.
(1) If $2^{3} \mid \overline{a b c}$, and $5^{3} \mid(\overline{a b c}-1)$, then
$$
\overline{a b c}-1=125,375,625,875 \text {. }
$$

Only $\overline{a b c}=376$ satisfies $2^{3} \mid \overline{a b c}$, meeting the condition.
(2) If $2^{3} \mid (\overline{a b c}-1)$, and $5^{3} \mid \overline{a b c}$, then
$$
\overline{a b c}=125,375,625,875 \text {. }
$$

Only $\overline{a b c}=625$ satisfies $2^{3} \mid (\overline{a b c}-1)$, meeting the condition.
Therefore, the sum is $376+625=1001$.