to get by those freaks you can just wait them out and try to slip through unnoticed, or try to kill them if you promote well and get a lot of xp attacking and winning
well, i hold onto them as long as possible with a skeleton in them, but that is pretty much abandoning them as theyll bring more than enough to beat that.
the hill cities are much more defensible and the ai will usually stop after taking a city each for a while.
summoning hyborem is good, it works out nicely too, but you can do damage a lot more places faster with mages. if i go for hyborem i go for him right off, the 3 main routes to victory seem to me to be sorcery, or priesthood, or infernal pact. combining them can work, but i find any one of them alone is usually enough to start destroying your enemies
theres also a healing salve item out there that might be able to heal the paladin, i cant remember how much of his curse it heals tho