Making mercs harder to find goes against the reason they are in the game to begin with, which is to make sure the player has some access to decent troops.
Never had the need to hire mercs before in a play-through which is why I'm suggesting they give them another reason to exist. Finding troops in towns and villages is quick and easy and only gets easier as the relations increase as you get more per visit and at high tier.
If one was to buy mercs early game for some quick decent troops, which I assume is what they are intended for and as you said, it makes them redundant for the rest of the play-through i.e. mid and late game, which the the majority of the game.