I say we add "Renown" into the game, you'd gain it in cRPG/Strategus battles by, guess what killing people(or wins?), maybe some small factor of 1 point of renown per kill(or win on a battle map, that would be more like the "game")
Renown would generate recruits for your personal strategus army, so the effect would be say if u were some guy like Goretooth, you'd be constently attracting a stream of bandits/mercs/followers to join you
this actually makes more sense than having every scrub toil to slowly recruit men, because honestly a famous name recruits men faster than 30 scrubs asking people to sign up
it would also maybe give individuals a chance to raise raiding parties, etc
either way, even if it doesn't do that exact thing, add renown, more messages to get in battles, etc, all past ones are fun and add interesting element to the game