There are some nice and very useful ideas here. Really enjoyed reading, but I have somewhat different look at this issue, so let me add to this my 2 cents how I view the whole procedural NPC behavior. Maybe someone find it interesting.
I would like to propose an idea that all complex NPC actions (including, but not limited to fleet operation, tactic and strategy) are emergent properties, based on core NPC behaviors, preset in some procedural or “hard-coded” fashion.
Single Non Playing Character is a core entity with the set of rules of behavior, defined procedurally, but based on some
social theories we have so far.
NPC behaviors and resulted causes are based on core set of rules associated to that race/entity/group. All stem from this.
NPC feet tactics is a subset of general NPC behavior. When certain complexity is achieved, some already mentioned additional rules could be applied (mainly to cut cost and ease on CPU time).
NPC complex emergent behavior could be influenced and radically changed by broad and all-pervasive “behaviors” of “higher entities” such as: Corporations, Empires, Religious/Ideological organizations, Guilds, Race's innate inclinations or “Deep Secret, beyond players understanding”.
As you see, it's a "low-level" stuff and the main theme here is “emergent property or new quality of the system”. There is a lot more about this, but I don't want to be boring.
Just something to think about:)