Does it need to work? Are we required to believe that the Scalosians managed to breed even once?
I mean, the external trappings of civilization are still doing pretty well on this barren planet, as if somebody had been maintaining them fairly recently - yet only a tiny handful of Scalosians survive, and they surely have better things to do than keep fountains bubbling. On the other hand, the Scalosians we see still appear fairly inexperienced in what they do, debating how much to tell their victims, or how much compassion to show. Yet Neela says several starships have been hit so far.
So we're facing two prime possibilities. One, starships are bountiful in this unknown part of the galaxy and arrive quite frequently, yet still only once every Scalosian generation, leaving each boarding party inexperienced in their art; this allows for generations of reasonable length. Or two, just a tiny handful of ships have been hit so far, always by Neela's team, and the results are still brewing inside a handful of Scalosian women staying planetside; this calls for longer generations or even greater frequency of arrivals. But in both cases, the calamity that rendered Scalosians sterile is only in the fairly recent past by human standards, and for this reason the cities still stand.
The option that the Scalosian society is accustomed to this lifestyle of sperm piracy, still doing fine, and maintaining its cities is less likely than these two, because there's no evidence of greater personnel resources than the small team we see, and the size of the team is the only factor allowing Kirk to overpower the intruders.
Timo Saloniemi