Well technically you don't need the petrify guy to clear capitals as the Legion any more if you are playing on the Rise of the Elves (latest d2 version). There the overlords got buffed and deal 30 blister damage as a DoT and also have 50 initiative, which makes them absolutely great.
And yeah the game is pretty awesome. I remember I didn't enjoy it that much when I was younger because of impatience probably. I'm also on the Legion campaign now 3rd mission I think. On the first one I decided to check out the witch (polymorph) and my party turned out pretty weak (caster leader, witch, 2 berserkers) so I could not actually kill any of the comp's main leaders as they both had 2 upgraded crossbowmen in their parties and decimated my back row as soon as battle commenced. So I had to bait them all the way next to my capital with level 1 leaders & summons away from my main guy who was exping in their territory undercover until the messenger came along
Next two missions I think it's pretty crucial to utilise the Bethrezen kid in active duty because the comps seem to start with 5+ rod planters and by week 1 have control of all resources. So you really have to hunt those bitches down, while your main is busy farming xp. He's also good when you have pretty much pacified an enemy, because his party can easily clear out their weekly new heroes. I used to do this with spells only with the mt clans (valkyrie is amazing and only 150/150 mana), but the legion spells suck donkey dick compared to the clans. Every mission takes an extra 20 days because no free 100% movement speed restoration per turn
