@Eschaton Right on. You brought up some good questions. I think such a system would be able to hit the mark, both in RPGM implementation and in whether it's fun.
For implementation, a plugin would definitely be the best way to go, but it could also be evented without extreme trouble. The implementation could either use States (added via Troop eventing, probably at the beginning of battle) which increase/decrease stats or give additional skills/effects based on the zodiac connections made with friends and enemies... or it could use two different sets of 'Elements' (one for damage skills and one for healing/support skills) and every skill assigned to a battler would be given that element (meaning that multiple versions might be created for the same skill as given to battlers with different zodiacs). It's certainly not easy without the use of plugins, but the point of a flexible engine is to allow you to take the time and implement the hard stuff.
Even the plugin approach wouldn't be too hard - I feel like it's something I could write within a day; maybe more if we wanted a lot of visual indicators for player clarity. The hardest part, honestly, would probably be the design aspect: how to design the bonuses/advantages so that they offer enough incentive to use different team compositions against different troops, but also are not so extreme that they create a binary win/lose based on what team composition you're using.
As far as fun - this is obviously subjective, but I think a lot of the fun would come from the way that the player is encouraged to work with a new team composition in different battles/dungeons. It's like being asked to solve different puzzles with different combinations of tools - 'improvisation' as it's sometimes called. You have to think a little to figure out how to best leverage those tools - and when you figure something out and get into a great flow where your characters are maximizing their potential, it's going to feel really good.
As Nietzsche wrote: "
What is happiness? — The feeling that power increases — that a resistance is overcome." When the implicit 'puzzle' presented by battle is the same each time, you're only really overcoming the resistance once, then you're just implementing the same solution ad nauseum. But when you're constantly asked to do it a little differently because a few pieces of the puzzle change, you can gain that fleeting feeling of happiness again and again. I think that's why improvisation is a really good tool for achieving 'Fun' in video games.