How you are allowed to "solve" the mission.     <------------This is all you need to modify.

Solution A -

I.E. Since maps are already destructible environments, how about adding the possibility of lost access routes around large rooms so if you are playing a crusader you could still fulfill the stealth aspect of the mission without changing your skills/talents spec ?

You could also allow the possibility of cutting your own passage through the walled sections to bypass a large area.

Solution B -

You could also allow another mission specific item type, "Pulse beacon" - This item when placed would cause all units within (X distance on the map) to move to it and investigate it as a distraction and once that directive was fulfilled they would slowly trudge back to their original starting locations.

I am not suggesting this feature for every single mission type or tile set, just the ones that would require a more subtle approach would have these as possible "options" on those mission types only.

If i sat here and really thought about it i could easily come up with 20 more variables for mission dynamics but i am merely attempting to illustrate that if you change how you approach something you can always find a way to adjust it without breaking it. 

=)

"Venerate the Immortal Emperor"

Good idea, but would require all builds\classes to have a stealth power. Atm if you do a speed run you only kill or attack what you have to anyway. With traps or consoles you will always have to attack something breaking any surprise.

There is the beacon story quest, more like it I can see happening but that's a close as i can see happening.