Another idea this time poached from Eagle Radiant Cross mod,
You could make different types of recruits depending on which town or village you go to. Certain towns or villages could contain specialty units not available in other places in the faction, and unless you gain relation with the town/village you wouldnt have access to these units.
in the ERC mod, i think the towns give out higherlevel recruits but maybe you could just make them location specific, they could be named like, "Saragoth Berserkers" or "Velucian Pikemen" with their own troop trees.
----
It might also be interesting, although potentially impossible to code, to somehow make your own skills affect the types of units available in a village through the 'train the peasants' quest. Again, probably not possible, but it would be sweet to create custom unit types in game (maybe like the way you customize npc heros?).