I realize that if you could do this you could hire mercenaries from alot of different places and you may be able to build up your force too quickly. My answer for that is fewer mecs available at a time. You often get a choice of 4 units or so. If there were only one, this would help. You could find a unit in more places, but you would only find one.

There rarity of them could increased as well. Inns are relatively cheap, I wouldn't feel cheated if the nercs were staying at my inns less than now if I could find them in more places. This would need to be balanced of course. There is a point, after which I would start to feel cheated if I VERY rarely found them.