Bandit hideouts should gradually gain "points" over time, which would be used to create bandit parties at random intervals. Point gain could be influenced by local conditions. Depending on the interval since the last group spawned, the size of the bandit party would vary. That way, you've typically got a number of tiny groups that can be engaged solo by a starting player but are only a minor threat to peasants, a few medium sized groups that are a serious threat to peasants but not capable of taking on caravans, and one or two big groups that are a challenge unless you've got a fairly sizable army backing you. The small groups would be fast and hard to catch by a large army, while the big groups would provide experience for the AI lords, assuming that the AI lords actually go after the bandits.
Basically, as long as the lords (or the player) clear out those bandit parties faster than the points can respawn, the bandit presence will remain small. Neglect them, and they keep building up into a real problem. If the hideout is destroyed, it should take time until there are enough points to build a new hideout, then begin releasing fresh bandit parties again, so a new hideout can't appear right next to where you just destroyed the previous one. You could never eliminate bandits completely, but could keep a region mostly bandit-free with enough effort.
A castle with a garrison over some minimum size (like 150 men) should be able to release a patrol of 10-50 men (randomly sized for the AI, player defined for an owned castle), one per castle.
As said over and over by poster after poster, tying bandit party size to player character level is a terrible design decision. Personally, I feel that "one size fits all" is another terrible choice; there should be a variety of different size bandit parties, regardless of player level or faction rank.
Whatever we're waiting for, there are some parts of the map, related to the type of bandits too (thinking to steppe bandits, sea raiders) that must be a nightmare for peasants... and probably caravans too.
There are some villages for which, I'm really asking myself how a group of villagers can ever reach the town they are supposed to go to...