How about:
- Removing the contracting out feature altogether. I can't remember the last time I used it, and it's really just unneeded complexity.
- Reworking the way they get promotions. How about every mercenary is added to the pool with 0 experience and then gain experience at a fixed rate as long as they stay unhired.
- Basing the price on the production cost of the unit, with experience playing a smaller part.
- Change names from "regional": "saxon", "minoan", etc to "mercenary company" ones: "Roger's", "Steel-gloves", "Dove Company",
"Great Company", etc.
- Making mercenaries way more common. Mid-game there are almost never any for hire. There is currently a restriction that mercenaries should not be more than 10% of the total units. How about removing this restriction completely and instead add more mercenaries whenever there are less than say 10 unhired ones and remove mercenaries whenever there are more.
- And finally implement regional mercenaries. They should probably not count toward the maximum unhired mercenaries since not everyone can hire them.