Answer: 199

Small Hint:

A regular $n$-pointed star joins every $d$th of $n$ equally spaced points on a circle, where $d$ is relatively prime to $n$

Big Hint:

Exclude $d = 1$ and $d = n - 1,$ which give a convex polygon, and note that $d$ and $n - d$ trace similar stars

Solution:

The congruent angles and congruent segments force the vertices of a regular star to be equally spaced on a circle, visited by taking a constant step: number $n$ equally spaced points $0, 1, \ldots, n - 1$ and connect every $d$th point. The path visits all $n$ points exactly when $\gcd(d, n) = 1,$ and the segments actually cross (making a star rather than a convex polygon) exactly when $2 \le d \le n - 2.$ Steps $d$ and $n - d$ trace the same figure in opposite directions, while different values otherwise give non-similar stars, since a dilation matching the circles would have to match the turning angles.

For $n = 1000 = 2^3 \cdot 5^3,$ the number of $d$ with $\gcd(d, 1000) = 1$ is $1000\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 400.$ Removing $d = 1$ and $d = 999$ leaves $398$ values, which pair up as $\{d, 1000 - d\},$ so the number of non-similar regular $1000$-pointed stars is $\frac{398}{2} = 199.$