Answer: 610

Solution:

In any optimal collection there are at most $9$ pennies (ten pennies could become a dime) and at most $4$ dimes (five dimes could become two quarters), so its dimes and pennies are worth at most $49$ cents. Hence an optimal collection uses either $q = \lfloor N/25 \rfloor$ quarters, like greedy, or $q - 1$ quarters. For an amount $v$ made only of dimes and pennies, the best count is $f(v) = \lfloor v/10 \rfloor + (v \bmod 10),$ which is what greedy does on the remainder.

Let $r = N \bmod 25.$ Greedy uses $q + f(r)$ coins, and the only rival uses $(q - 1) + f(r + 25)$ coins (possible when $q \ge 1$), so greedy fails exactly when $f(r + 25) \le f(r).$ Tabulating: for $r = 0, \ldots, 4,$ $f(r+25) = r + 7 \gt f(r) = r;$ for $r = 5, \ldots, 9,$ $f(r+25) = r - 2 \le r;$ for $r = 10, \ldots, 14,$ $f(r+25) = r - 2 \gt r - 9;$ for $r = 15, \ldots, 19,$ $f(r+25) = r - 11 \le r - 9;$ for $r = 20, \ldots, 24,$ $f(r+25) = r - 11 \gt r - 18.$ So greedy fails exactly when $N \ge 25$ and $r \in \{5, \ldots, 9\} \cup \{15, \ldots, 19\}.$

Each residue class mod $25$ contains $40$ values of $N$ in $1, \ldots, 1000,$ so these $10$ residues give $400$ values, of which the $10$ values less than $25$ do not count (there $q = 0$). Greedy fails for $390$ values and succeeds for $1000 - 390 = 610.$