The original version of "Errand of Mercy" allowed some leeway, since the Federation fleet facing off with the Klingon one was never shown thus it was easy to imagine it consisting of some sort of hastily organized task force of different types of ships like destroyers, frigates, light cruisers, etc. with maybe one other Constitution at the most. Yet remastered TOS (which I've always been lukewarm about) retro-conned this by showing the fleets consisting of identical Federation and Klingon ships and thus destroyed this theory and making one have to accept the unbelievable premise that Starfleet was able to send at least half the amount of their best starships to Organia on short notice.
I wholeheartedly agree. Let's ignore TOS-R, please.

Also, doesn't the plaque on the bridge say "Starship Class"?
I think Franz Josef hit on a good solution: There were 13/12 ships in the fleet in the first year of Trek, but by the second/third year, more had been built.
Without TOS-R, and leaving aside "The Ultimate Computer", since that was put together specifically to compare apples to M5-enhanced apples:
"The Doomsday Machine" -- we never see the bridge, and the NCC # is waaay off of the Enterprise's -- is it possible the Constellation is actually an older class of ship? "But it looks the same!" Well, I can't tell a Kitty Hawk from the Enterprise or the JFK. So I can imagine the two being different ships. They certainly don't have to be the same class.
(Note: Decker is a 'starship' commander. He might also be a 'Starship' commander. If he were definitely described as the latter, that would be more conclusive that the Connie and the Big E are the same class).
"Obsession" -- the Farragut is explicitly a 'starship' but not necessarily a 'Starship'. Same deal as the Constellation. In any event, Kirk served on it, but the Enterprise never encounters it. As for the Yorktown, no class is assigned it at all. It could be a Columbia class ship, or a Class J freighter... or anything!
"The Omega Glory" -- pretty definitively a ship of the same class as Enterprise. But it's second season so there might be more of that class roaming about.
"The Tholian Web" -- ditto... but it's third season, so it is even more likely that there are more of that class roaming about.
"The Immunity Syndrome" -- it is never stated what class the Intrepid is. Only that it has a crew complement of 400. That's similar to that of the Enterprise, but lots of ships have similar complements (frex the U.S.S. Enterprise and the U.S.S. Kitty Hawk).
Obviously, your Doylian interpretation is the correct one, and it would, indeed, have been nice to see more kinds of ships. That TOS-R wasted the opportunity and went the other way is yet another mark against it.
But from a Watsonian perspective, the Enterprise only conclusively crosses paths with a ship of its type out in the reaches of space twice.
That doesn't seem such a stretch to me.