It's always "bigger than we can afford to show you", but beyond that, DS9 gives us the most accurate numbers for any era.
In the Dominion War, Starfleet operates in Fleets, of which the 10th is the highest-numbered. Statistically, it would be odd indeed for there to be more than a dozen fleets when we never hear of the higher numbers.
An individual Fleet features hundreds of ships, the lowest we hear of being the 7th at Tyra with 112 ships in "A Time to Stand". "Elements" of the 2nd and 5th Fleets amount to 600 ships in "Favor the Bold", though, suggesting normal strength is more than 300 ships.
We're talking about a big and muddy ballpark of four or five thousand ships taking part in active frontline fighting in the Dominion War, then. Which jibes well with the Klingons being able to mobilize some 1,500 ships for a specific major offensive later on.
Earlier Starfleets probably had fewer ships. Using the German Tank Problem coarse statistical approach, an organization that has ships with registries around NCC-1800 in the 2260s would have built somewhere around 2,000 ships with NCC series registries overall, which is probably as good a guesstimate as any; some of those would be long retired by the time of TOS, while some would have been added to fleet strength from Romulan War surplus and refitted so many times that they'd be departing in a serious bout of block obsolescence around the time of TOS at the very latest, allowing for a construction surge even if nothing else changes. But perhaps the end of the conflict with Klingons around the TOS movies allows the UFP to expand like never before, adding to the surge?
Around 2,000 ships for the first century of UFP Starfleet ops sounds fine in terms of what we see on screen, and in lieu of actual hard numbers anywhere. If there are more, we have to come up with explanations as for why they aren't given NCC registries. Such as, NCC was for human ships only originally, and a quarter of the strength came from Andorian ships that had FHH registries instead. Or there are plenty of ships that aren't part of the fighting strength, and in the early days those didn't get NCC numbers while in the DS9 days they do, or whatever.
What Starfleet would do if it had, say, four Fleets of 500 fighting ships available as DSC or TOS starts... Well, some of those would be out there on exploration errands. But having a thousand ships operate a thousand lightyears from home would still leave most of the volume of that 1,000 ly radius sphere unexplored, if a ship can only scan to the sides of her flightpath by a couple of lightyears. Plenty of stuff left for later heroes to discover.
Timo Saloniemi