I think the outlaws need to be upgraded in a feasible cost / benefit relationship.
I thought that they could be more devile and faster to hire, but with a limit of creation and that they do not cost population. They could be like natives, but they cost coins.
The limit of creation and its power could extend as one gets older. They could have a creation limit of 15-20, starting at age 2 with a limit of 5-10.
I think that this way they would be relevant throughout the game.