Alright, think I know what I need to fix.
About their patrols, they are upgraded in the same manner as yours: based on their leaders Training level and over time. So if left alone they'll improve, or if their leaderhas training skill.
Though it might be worth giving the AI heroes a little extra training skill when they become Lords/Ladies and Kings/Queens.