It's not exactly out of nowhere. Every faction gets 3000/turn (consider it resistance donations by the nobles resenting your occupation) even if the faction has no taxable regions left (some turns after a faction has lost their last settlement they starve to death though). That merc army I saw appeared a few turns after I had defeated the faction's last visible stack. 3 turns x 3000 = 9,000: quite enough to hire a merc army.
Bookmarks