History aside, there's nothing unusual about this. Many of the mercenaries are the former troops of other monarchs. The inns that will have most mercenaries are those that are close to battle zones. Units that are disbanded or otherwise lost often show up in nearby inns as mercenaries.