I agree. The current Maelstrom Missions are completely random and makes the game devolve into nothing but lucky card draws. Might as well just roll a die each turn and on a 6+ you get a victory point.
I think an army specific, tiered secondary objective system would be good. Very close to the Malifaux 1.0 Strategy and Schemes system.
Each player would have an option of picking their secondary objectives. Then, if they complete it two more options become available. Then depending on which of those they chose (and completed) two more options would become available, etc. All the while each subsequent objective was somehow related to the previous objective.
An example for Space Marines would be the following "narrative" secondary objectives:
Quell Rebellion Secondary Mission
1.) Assess Enemy Forces: Get a scoring unit within 12" of an Enemy Unit (18" for scouts).
2a) Neutralize Enemy's Support: Destroy an Enemy Heavy Choice
3a.a) Reconnoiter Enemy's Supply Routes: Get a scoring unit in enemy's deployment zone.
3a.b) Decimate Enemy's Command Structure: Destroy an Enemy HQ or Elites Choice.
2b) Suppress the Enemy: Destroy at least 2 enemy unit during the shooting phase.
3b.a) Flank Enemy: Destroy an enemy unit with a fast attack unit.
3b.b) Assault Enemy: Destroy at least two enemy units during the assault phase.
Thats just an example I thought up right now, to give an idea how the secondary objectives could work. This way the narrative is actually part of the game play.