I think that you're all forgetting the Arthurian legends. Lancelot du Lac was a knight errant (and the best example of what a knight/paladin should be until he fell). The adventures of the Green Knight followed by his nemesis of a beast (whatever its name, too long). What about Galahad? They were all "questing" just like our adventurers are doing. Even in the old medieval times, there were mercernary for hire, bounty hunters (their task was usually to bring the head of their querry). Remove magic and the dark ages/medieval and early renaissance was a bit more outlandish than you give it credit for. Nobles were ready to hire mercenaries (adventurers?) so as to not risk their own men. You need your loyal men in case of a rebellion or an outside invasion. Becauise of this, losing a man that is loyal to you is way worst than losing a man for hire. Even in the late renaissance there were men for hire. Think about Pirates, Bucaneers and Privateers. Instead of the landlock bandits/mercernaries, they were doing the same thing but they were called different names because they were on boats/vessels. Countries (and nobles) were giving these men a litteral immunity for whatever they were doing while under their employment.
Even the romans were using auxiliairies (read here mercenaries) in their armies. Some men were professional slave hunters and they were often hired to find criminals too. Its not because the "cowboys" are the closest known exemple of what our adventurers are doing that there was no examples of the same behavioral patterns in previous erra. And we should mention that there are mercenary companies/units/squads in our time too (and, unfortunately, assassins for hire).
I would tend to agree that in previous editions, the players were more less "immune" to what the lawful leaders could throw at them (especialy at a higher level). That is no longer the case with bounded accuracy. Also do not forget the assumption that the players are supposed to be heroes (or anti-heroes, I know that there are variations). We must not view the petty baron with our modern eyes. We must see him through the eyes of medieval times. Rank is fairly imbeded in the minds of that time. The players should respect him unless he's a total jerk. Even then, they should simply walk away and not work for the jerk again. On the other hand, the petty baron isn't stupid, if that band of adventurer/mercernary could do what his men could not, he will show a healthy respect. And if your heroes are out of control, isn't it time for brave bands of adventurers to do the job of removing this evil treath from the kingdom?