As far as I can ascertain there’s around 1,500 faction exclusive quests out of a total of 4,244 within the game: Around 750 for Horde and 750 for Alliance, the remainder are for both factions.
But there’s no data on exact numbers, or at least none that I can find.
Regardless people who are totally new to Classic may often find themselves running out of quests no matter what faction they play. There are two main reasons for this.
First, some players tend to ignore lower level quests. They assume that “only yellow and above are worth doing” and ignore green quests, despite the fact that green quests still give plenty of XP. In some cases it’s even worthwhile to do grey quests, in the knowledge that it’s part of a chain that will eventually get harder and lead to yellow or even red quests further down the line.
Second some players don’t understand the need to zone-hope within Classic. They assume that going to more than one zone of roughly the same level and questing there is a waste of time - so, for example, they’ll complete Tanaris, but never to Hinterlands or Feralas, instead moving straight to Un’Goro.
Another issue is that it’s never a bad idea to mix a certain amount of additional mob-slaying in with your questing, for example if travelling from Kargath in the Badlands to a quest location, slay the mobs that you encounter on the way, rather than just running or riding past them.
The only real time I ever encounter a slight ‘quest drought’ in Classic is around L58-60, in which the questing becomes a bit scrappy and the remaining available quests are mostlly group quests, or tedious collection grinds in Silithus. But there’s always enough for me to get through, though it can get a bit tight at L59 when I find myself grubbing around in Western Plaguelands for those last few points wihout having to resort to pure grinding.
I’ve certainly never had a quest drought at 35-40, if anything there’s too many quests around that level! STV is absolutely teaming with so many quests you can’t even fit them all in your log, and then there’s Desolace, Swamp of Sorrows, Shimmering Flats and Badlands to boot.