This problem can be reduced to solving
$$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9, \quad x_1 \neq 0, \quad x_1 \neq 9$$
First, we solve
$$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 15$$
This is a standard stars and bars problem, with solution $\binom{15+3-1}{15} = 136$. Now which solutions are wrong? Well, first of all those with one of them above $10$. But if, say, $x_1 \geq 10$, then we can write $x_1' = x_1 - 10$ and $x_2' = x_2, x_3' = x_3$ to reduce the problem to
$$x_1' + x_2' + x_3' = 5, \quad 0 \leq x_i' \leq 5$$
This is again a standard stars and bars problem, with solution $\binom{5+3-1}{5} = 21$. Since exactly one of $x_1,x_2,x_3$ could be above $10$, this gives $3 \cdot 21 = 63$ wrong solutions in total. So there are $136 - 63 = 73$ solutions to
$$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9$$
Finally, we need to subtract $4$ solutions with $x_1 = 0$ (i.e. $(x_2,x_3) \in {(6,9),(7,8),(8,7),(9,6)}$), but also subtract $7$ solutions for $x_1 = 9$ (i.e. $(x_2,x_3) \in {(0,6),\ldots,(6,0)}$). This gives $62$ solutions in total.
So you have at most a 7-digit number (since 10,000,000 isn't a possibility): X-X-X-X-X-X-X, and the 12 can be in 6 different positions, so you have 1-2-X-X-X-X-X, X-1-2-X....,X-X-X-X-X-1-2. That is a total of $6*10^5 = 600,000$ different numbers. Now the hard part like I said above is finding the overlaps.
Suppose 12 were to appear twice, that means that we have 3 open spaces otherwise. How many ways can we reorder the two 12's and the extra 3 spots? That would be ${5\choose2} = 10$. Since the open spots can be $10^3$ different numbers, we end up with $10*10^3 =10,000$ overlaps.
Suppose 12 were to appear three times, that means we have 1 open space otherwise. How many ways can we reorder the three 12's and the extra spot? ${4\choose1} = 4$. Since the open spots can be 10 different numbers, we end up with $4*10 = 40$ overlaps.
However, if 12 were to appear three times, that means 12 also appears 2 times, and so instead of have $10,000$ overlaps (from the first overlap case), we actually have $10,000 - 40 = 9960$ total overlaps.
With $10,000,000$ different numbers, we end up with (total numbers - total overlaps) = $10,000,000 - (600,000-9960) = 9,409,960$ which I verified with Java.
Best Answer
Clearly, $1000$ has digit sum less than $15$.
By appending leading zeros as necessary, we can represent any nonnegative integer less than $1000$ as a three-digit string. For instance, we can represent $17$ as $017$. Notice that appending leading zeros does not change the digit sum.
Let $d_k$ be the $k$th digit. Then we want to find the number of solutions of the inequality $$d_1 + d_2 + d_3 \leq 15$$ in the nonnegative integers subject to the restrictions that $d_1, d_2, d_3 \leq 9$. We can transform the inequality into an equation with the same number of solutions. Let $$s = 15 - (d_1 + d_2 + d_3)$$ Then $s$ is a nonnegative integer and $$d_1 + d_2 + d_3 + s = 15 \tag{1}$$ Equation 1 is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of three addition signs in a row of $15$ ones. For instance, $$1 1 1 1 + 1 1 1 1 1 1 + 1 1 1 + 1 1$$ corresponds to the solution $d_1 = 4$, $d_2 = 6$, $d_3 = 3$, $s = 2$, while $$+ 1 1 1 1 1 1 1 1 1 + 1 1 + 1 1 1 1$$ corresponds to the solution $d_1 = 0$, $d_2 = 9$, $d_3 = 2$, $s = 4$. The number of solutions of equation 1 is $$\binom{15 + 3}{3} = \binom{18}{3}$$ since we must select which three of the eighteen positions required for fifteen ones and three addition signs will be filled with addition signs.
However, these solutions include those in which one of the variables $d_1$, $d_2$, or $d_3$ exceeds $9$ (we do not care if $s > 9$ since it does not represent a digit). Notice that at most one variable can exceed $9$ since $2 \cdot 10 = 20 > 15$.
Suppose $d_1 > 9$. Then $d_1' = d_1 - 10$ is a nonnegative integer. Substituting $d_1' + 10$ for $d_1$ in equation 1 gives \begin{align*} d_1' + 10 + d_2 + d_3 + s & = 15\\ d_1 + d_2 + d_3 + s & = 5 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{5 + 3}{3} = \binom{8}{3}$$ solutions. By symmetry, there are an equal number of solutions of equation 1 in which $d_2 > 9$ or $d_3 > 9$. Hence, the number of solutions of equation 1 that violate the restrictions $d_1, d_2, d_3 \leq 9$ is $$\binom{3}{1}\binom{8}{3}$$ Therefore, the number of nonnegative integers less than $1000$ that have digit sum at most $15$ is $$\binom{18}{3} - \binom{3}{1}\binom{8}{3}$$ so the number of nonnegative integers that are at most $1000$ that have digit sum at most $15$ is $$\binom{18}{3} - \binom{3}{1}\binom{8}{3} + 1 = 649$$ Your proposed answer of $725$ suggests that you did not take into account the fact that the leading digit of a two-digit or three-digit number (as opposed to string) cannot be zero.