MArcomage

Yes, it's time. I tried this combination and I'm not happy for how it works though I can easily win 3 games of 4 with this deck.
This deck isn't like Undead - Holy is relatively weak keyword, and Soldier returns only recruits cost. Undead also has much more attack potential than Holy/Soldier because of Undead host and many rares with heavy attack. The only Holy rare with high attack is Avenging angel, and this is very situational card. But the thing is that Holy/Soldier doesn't rely on rares by any means.
We have 6 Holy/Soldier cards: Crusader, Fanatic, Knight templar, Paladin, Temple guard and Zealot - main Holy/Soldier weapon. Plus Guardian angel that doesn't have Soldier keyword itself, but has it as a support keyword. Plus Heresy that can give you up to 3 Fanatics and Death before dishonor that turns Fanatic into Zealots (and Zealots into Guardian angels, but that's not so needed).
With all of this usual N for Zealot and Guardian angel is 11-13. 43-49 attack for Zealot, 33-39 attack and 44-52 wall for Guardian angel - and these cards are not very expensive unlike Undead host. And don't forget that we are talking about Holy, so we can use Fairy, Angel, Benediction and Priest as resource support and Crystal golem as defensive card (24-30 wall from a common!). Mass replacers like Elemental storm? Doesn't work because Holy decks usually have Purifying fire.
I can compare Zealot only with Keeper of souls. Keeper of souls is definitely strong both in Beast and Burning decks. But even with recruits returning, even with additional attack from Beast and Burning in enemy hand Keeper of souls is weaker than Zealot. You can't summon Keeper of souls with guarantee, you have only one more Beast/Burning card that is near to useless, and Zealot modifier is higher so Zealot still inflicts more damage. Same story with another Beast - Forest spirit. It's a strong card, but Zealot deals twice as much damage as Forest spirit, and Guardian angel builds much more wall, not to mention that Guardian angel's attack is higher too. Moreover, when you play Forest spirit, you even can't hope on N >= 12, only 9-10, because it relies only on your hand, and there is only one more Beast/Nature card.
Remember discussion about one single Corrupted woods and Nature strength? Holy/Soldier is much stronger than Nature was. With that synergy, stock increasers and defensive capabilities it is even stronger than Undead that I still consider overpowered.
The worst thing that I can't suggest any ways to nerf it except multiplier decreasings for Zealot and Guardian angel and removing Soldier keywords from Temple guard and maybe Fanatic. Maybe you can suggest anything?

My first deck to win was soldier holy, and yes, zealot and guardian angel are tough. I would nerf only guardian angel though.

And about soldier token, it's not weak. Yesterday someone wiped me with barrage of soldiers while i was trying to rebuild the damage with lots of good tower/wall cards. His recruit count almost not dropping.

I'm not saying that Soldier token is weak. But Holy cards needs some gems as well as recruits. Soldier can't return it, and Undead is returning all types of resources spent.

Holy don't need that big amount of gems, the gems you conserve from playing Soldiers, can be used to play Holy cards. And when you have cards like Fairy and Angel, then you don't really have a problem with stock. Add a few good Soldier support cards and +recruits and you are set. Holy/Soldier depends a lot on what kind of supporting cards you got in your deck, and a Holy/Soldier deck has a different gameplay approach to Undead. Undead have high-costing high-damage cards. Soldier is based on having moderate-damage moderate-to-low-costing cards that can keep coming like a barrage against the enemy. Also, there's a lot of Charge cards you can utilize. Honestly, I have a deck Holy/Soldier and with cards like Wheat Farm, Draft and Colonialism, I can keep throwing Soldiers at my enemy. The strategy I have is to amass something like 20-30 recruits beforehand (a matter of 2-3 rounds) and then start bashing my enemy, while keeping the keyword work for itself. Throwing the occasional Fairy in to boost my economy and Divine Intervention for defense. Also, if you have Temple of Life and Prayer, you've got a good chance of getting rare Holies, which are always welcome.

On the other hand, I'd go as far as to suggest that Holy/Soldier is overpowerd in some cases, especially since recently that we've made Fanatic and Zealot into Holy/Soldier and can be combined further with Guardian Angel

And don't forget that Undead is returning all resource types because it uses massive amounts of both gems and recruits. Holy cards are quite cheap on the other hand. In fact, on Holy/Soldier deck I have, gems are the least I need (1.82 gems per turn according to Arcomage calculator, compared to 4.8 recruits and 3.9 bricks per turn)