In SG-1, they find the Abydos cartouche in the first episode, which gives them an estimate.
There are certainly many gates NOT on this artifact.
With the number of chevrons on the gate, and the number needed for dialing (six + Point of Origin) we can determine the number of potential gates (1,947,792 - 36 choose 6)
We can discount the random dialing the US did pre-Stargate movie - it's highly unlikely they dialed a significant number of gates using the correct 7th symbol, without which the gate would never work.
The stargate team doesn't regularly dial random numbers to try to find valid addresses. This indicates to me that they consider the odds of randomly dialing a valid gate too small to be worth the risk.
With that in mind, I peg the chances at 1% (a number for which I have no real reasoning beyond "small enough to be good, but big enough to be interesting"). It's also a nice, round number, and humans in general find those appealing.
So, assuming 1% of the possible gate addresses works (with some margin for error for buried or inaccessible gates) at approximately 20,000.
The next question is - how accurate is this estimate?
Not very - I have no support for my percentage estimate. I could be off by a significant margin (most likely in the 'too generous' direction). This could be considered an optimistic estimation, then.
Out of universe, I think this number would be called 'plausible' by the creative team in charge of the shows, as it leaves them a lot of wriggle room, enough planets for 100 20-episode seasons (assuming no repeat visits), etc.
Final Answer: 20,000 at best. (For a 37-glyph stargate)
16,500 for Pegasus (36-chevrons, though Pegasus may have a relatively higher percentage of active gates than the Milky Way)
Edit:
In Earth's network (39 glyphs): ~28,000 As someone pointed out in the comments, the Milky Way network has 39 glyphs per stargate, meaning we should do 38 choose 6 instead of 36 choose 6. The rest of the math is unchanged.