In the end, I destroyed eleven civilizations, and an AI destroyed a twelfth, meaning that over half of the civs in the game were used. For some reason, only certain colors were restarted, and this number dwindled, until restarts stopped altogether. It wasn't a date problem--I finished this game in 480 BC!! Nor was it a number-of-turns problem, because some colors stopped restarting while others did again and again.

Anyway, if there were a way to assure that the AI civs kept coming back, there would be no problem doing this "challenge" on lower levels. On Deity it would indeed be a challenge, perhaps more difficult than the OCC.