I finally won last night, on my third try. One of the best scenarios I've ever played on any mod or any game. I appreciate the help from Dreylin and others on this thread.
Playing on warlord level, I won on turn 402 (remember you start on 79, IIRC), and was rated Cthulhu level (the very top)! Knowing what I know now, I think it's definitely doable at higher levels, but I don't have the stamina for that. I spent about 10 hours on my first try, 30 hours on my second try, and the final successful try took 21 hours.
The northeast island you start on has room for 8 or 9 cities. I made 7 to make optimal use of resources. There is also a one-square island near your capital that can become a powerhouse. So that's 8 cities in the north.
Incidentally, I started on a northern island that had both reagents (needed for Archmages) and incense (needed for Priors, your only healers until you get the angel whose name starts with an S). You HAVE to have those resources and you CAN'T hold them on the mainland. So I suggest rerolling if your starter continent (or at last starter continent plus southern island) lacks these resources. Trust me on this.
The first strategic goal is to QUICKLY conquer the Clan island in the southest corner. I did that with just the one galleon ferrying a couple of loads of confessors and archers. When I took out the Clan, they had only 3 small cities. You should have this continent conquered by about turn 150 or sooner. This south island has room for 9 more cities.
So that's all you need: 17 cities on those two islands. You'll only ever keep one more city--when you start attacking Tebryn, you need one fortified city on a hill to do some attrition. Best city is the orange guys's city just a little to the SW of the Tebryn stronghold.
I doubt it is possible to win this scenario without the Luchuirp, so make sure to help Beeri in The Momus. I made all of my cities Luchuirp, except for one Lanun (to get Guybrush Threepwood) and one Bannor (to get Donal). However, I never ended up needing Donal, so if I did it again I'd do one Lanun and all the rest Luchuirp.
Also, I agree with Dreylin that you HAVE to go with The Order religion for this one.
Your build up before you start a-conquering the evil vassals is about 200 turns. It's VERY important to build wall to wall pirate coves, on every possible square. I must have had 40 of them. The island city near your capital can support 3. It's also VERY important to spread Order to all 17 of your cities. These are key infrastructure points.
Magic. As the Lanun, you start with Air, Chaos, and Water in your palace. I never used any of those very much. But the Lanun have the best palace IMO so I didn't change that. It's good to have Air and Water, because if you add Fire and Earth, you can build the Tower of the Elements and have extra strong elementals. I know a lot of people swear by Maelstrom (Air II), but I don't use it much. I only ever take one Water upgrade--your first adept should take Spring to turn all the desert squares on the northern island into grasslands. You don't need that for the southern island.
Okay, you have Air, Chaos and Water. You also get Law eventually from the Order holy building. You have two nodes on the n. island and three on the s. island. What to do with them?
You have to have Enchantment to repair the robots (golems). And you have to have Fire to give the fireball to the robots and to your mages. So that's what you build on the northern island.
What to do with the 3 nodes on the s. island. You HAVE to have Life for the Destroy Undead spell. It also gives a good health bonus. The final two are optional. I took Earth, so that I'd have all 4 elemental magics, so that I'd have stronger elementals. For the last one, I took Entropy, since Dreyil said this was necessary for the Rust spell (which is said to be useful for knocking down the bonuses of the evil Infernal Crossbowmen at the end of the game). However, every single time I cast Rust it was resisted, probably because I made generalist mages and didn't just make a few that specialized in Rust plus combat strength. Therefore, Rust was useless to me. If I played it again, I'd pick Metamagic, to boost all the other magic.
So my final magic lineup was:
Law - from Order holy bldg. (tablets of Junil)
Air - from Lanun palace
Chaos
Water
Fire - n. island
Enchantment
Life - s. island
Earth
Entropy (but I now recommend Metamagic)
As you can see from my note above, I wish I had more carefully specialized my mages. The key mage spells for this scenario are: Fireball, Repair, Destroy Undead (and possibly Rust if specialized for this). If you try to get each mage to do all of them, they're all weak. You only need 3 or 4 repair mages in your killer stacks, not 20 or 30 or more as I had. You also only need maybe 4 or 5 destroy undead mages in those killer stacks, not the many I had. Specialize. Build up strength and mobility.
Assassins. Dreyil was very helpful in advising to build assassins, so you can pick off Ritualists in close-by enemy stacks. I completely agree. But I built way too many of them (about 20). You could win the game with only four or five of them.
Heroes. Playing this way, you get Valin (from Order). Guybrush (from Lanun). Black Wind (from Lanun). And Donal, if you make a Bannor city, but I now think this is not necessary. The Black Wind is good for early dominance of the seas, but not needed in the late part of the game. You could get by the whole game with nothing but Valin. Make sure to take drill all the way down, and mobility, so that Valin can end up attacking several times every turn! At the end game you get Sphenor (sp?) the angel, a super unit. You could win without him, but he is VERY useful.
Healing. You can't heal the robots, but you can repair them. To heal living units, there are only three things I observed: (1) they heal a little when promoted; (2) you can build four Priors (high priests) if you have incense, plus Sphenor (sp?) the angel also heals; and (3) confessors have the useful feature called Spirit Guide that heals all units in their stack if they are killed. I found this very useful in the very early parts of the game.
Your armies are mainly lots and lots of fireball iron golems backed up by mages. That by itself is enough for everything up to the final battles.
I started attacking the mainland by the time I was about one-third done with my development of the south island. My main army quickly destroyed the Gosea (the blue ones to the east). It then swung north and attacked the light blue guys up there.
A second big army was then simultaneously sent from the south to attack the orange guys plus Hyborem.
The northern army swept south, and the southern army swept north, in a giant pincer movement, destroying everything.
I highly recommend wiping out Hyborem to get the +2 weapon Gela (which I gave to Valin) and to remove irritations on your flanks.
Keep the orange guys alive until you finish off Hyborem. The last orange city you conquer will be the strong one on a hill on the coastline just a little ways to the west of the stronghold of Tebryn's evil purple forces. This is the ONLY city you will ever keep or found on the mainland. Stick BOTH of your main armies in there for awhile to withstand the onslaught, because as soon as that city falls, and the border barrier is lifted, Tebryn will send wave after wave.
In my second try at this scenario, I was overwhelmed. I'd waited too long and there were simply way the heck too many evil guys, plus I didn't have proper preparation (such as Destroy Undead mages).
Dreylin said he got Valin to the end of the promotion tree. He spent a long time hunkered down on the mainland, protected by his own Crossbowmen, killing hundreds upon hundreds of evil forces. This didn't happen to me. My Valin was only about level 13 at the end. In my game, I only stayed in that orange city for maybe 15 turns while repelling Tebryn's hordes and gathering reinforcements of my own.
Then I went and wiped Tebryn out.
I found it surprisingly easy to wipe out Tebryn's forces--until I got to the core of his territory in broken lands.
I had my main army with about 40 units parked in a citadel bombing the Tebryn capital of Galveholm every turn. I sent about 30 units in a second army, nearly all golems and mages, up north to park in another citadel and bomb the city of Frost, three squares NE of Galveholm. Finally, a third elite commando group led by the angel took out all the Tebryn cities to the east.
I was planning to wipe out all other cities and then to attack the Tebryn capital from three directions with three armies. But it didn't work out that way.
Galveholm and Frost have some kind of unbelievable defense bonus plus an unbelievable regeneration bonus. Galveholm is on the coast, so my fleet reduced its defense bonus to 0 every turn. I razed surrounding citadelas. And still, I'd bomb it every turn with something like 25 fireballs and 4 fire elementals and never kill a thing!
Meanwhile, my golems and mages attacking Frost had the same problem. Hundreds of fireballs, and no progress at all.
After being frustrated by this for about 10 turns, I moved my major stack (with Valin and Guybrush) up from Galveholm to join the forces attacking Frost. The combined army had more than 70 units, and I was able to use Valin every turn (since the citadel is right next to Frost, while the citadels near Galveholm are 2 squares away).
That was enough. After about five turns I destroyed the city of Frost.
Then something amazing happened! The spreading blight of the infernal lands began to lift. Broken lands tiles started randomly turning back into normal lands every turn. (I forgot to check if my ability to self-heal came back.) PLUS, destroying the neighboring city of Frost DESTROYED THE DEFENSE BONUS in the capital! Once Frost was gone, it was RIDICULOUSLY easy to defeat the huge dragon Abbasi and the remaining defenders of the capital. Indeed, I bombed them from long range as I approached, and I had them all dead when I was still two squares from the capital! Once Frost was gone, Abbasi became vulnerable to fireballs! So I never got to see the epic battle of Valin vs. Abbasi that I'd pictured.
From all of this, I surmise that the eponymous Black Tower is actually not in the Tebryn capital at all! Instead, I think it's in Frost. Or in any event, there is SOMETHING in Frost that gives unbelievable bonuses to Frost and Galveholm.
Whew! What a brilliant scenario!
P.S. Just want to add one detail: At the end of the game, I had a HUGE population, despite only 18 cities. I had a 31 (my capital), a 30, another 30, a 29, and a 28. All of those were still growing. Lots of Great Merchants.