I've played Byzantium in Middle Ages, and I remember the Abbasid's invisible unit being a big pain. Maybe I just didn't realize how to counter them effectively, but they wouldn't be my top choice in the scenario for that reason.
Conversely, if I were to play on Deity, I'd definitely consider the Abbasids, as IMO they have arguably the strongest start. In a corner, so a lot of the border is secure, and a lot of territory. Moving relics for 10,000 VP isn't necessarily easy at lower levels, though doable if you focus on it, but making a successful landing on Deity sounds much more challenging, thus making England/France/HRE/etc. less appealing, though you could still win with them without moving a relic to Jerusalem. But at least for me, no one would be "too easy" on Deity. Except maybe Japan in WWII - Pacific, as that's the one scenario/civilization I've managed to win on Sid.
On another start I lost an enkidu warrior to a barbarian. I thought I had seen that 'preserved random seed' isn't checked for the Mesopotamia scenario. I had saved before, so I reloaded and fought it again and won. Then I doubted that. So, I reloaded and this time I lost. So, I'm very sure that 'preserved random seed' isn't checked.
The optimal war strategy clearly thus involves reloading until you get a leader in three attacks (or two if you have several of time). Several more times of reloading also, since leaders can rush infrastructure which aren't great wonders like normal.
Maybe I've missed something about such a competition being interesting. Such a competition definitely could be more about persistence to reload and play battles again. Even though some HoF games rely on map rerolling, reloading for leaders isn't something that happens there. I think Drazek understood the HoF concept best when he suggested that it's about playing the best possible map with the best possible strategy. Reloading the same battle over and over again, sounds different than making the best possible bet/probabilistic behavior doesn't it?
I do think that not having 'preserve random seed' checked was a good call by the game designers. It can be more fun to reload a battle sometimes. And it's a simple matter to not reload if doing that is not fun, or do such only in rare instances. But, still different than any competitive play substantially.
Yeah, I hadn't really thought through being able to start as many times as you please, versus not being able to replay a game for HOF/GOTM. Although I personally wouldn't have the patience to reload until getting 3+ leaders in short succession - kind of like how Lanzelot discusses not wanting to play almost the same map/civ twice in a row, I'd rapidly get bored reloading until I got sufficiently lucky. Which may also be part of why I don't have any top-tier HOF games, just table-filler games for the less popular configurations.
So, yes, with a sufficient amount of patience to be blessed by the RNG gods eventually, it's not very interesting. But the basic question of, "who's the strongest civ in the Mesopotamia scenario?" is still an interesting one or no one would be discussing it. There's no 100% scientific way to determine that though, for reasons such as what you've mentioned.
If I wanted to set up a test for it to get some data on the question, I'd probably try to have e.g. 10 players each play each civ, with an honor system rule of no restarting/rerolling, and compare the results. It's entirely possible that such a trial might end with something like, "Well, the fastest time was Spoonwood's Medean game, but he got five leaders in the first five turns in that game, and on average across all players the Medeans were the third-slowest, so they probably aren't the strongest overall." Or maybe someone came up with an ingenious strategy for the Hittites that gives them the fastest time, and no one else tried anything similar, so they averaged out as somewhat slow. It wouldn't necessarily solve the debate, let alone because the ideal civ may vary by difficulty, but it would provide interesting discussion and highly debatable non-scientific data.