Q:

Semi-procedural mission generation

I want to generate missions out of more or less predefined smaller chunks. Example mission structure:
Mission type: Rescue

Travel through forest
Gather intel
Choice:

Sneak into castle (if it fails, switch to fight)
Fight your way into castle
Use clever disguise (if entry method available for castle and it was discovered in 2)

Rescue princess

The travel block is generic and could be applied to a number of different landscapes, giving different random encounters or events.
Same goes for other types of blocks, the castle could be replaced with another building/location, the princess could be someone else etc.
As the example hints I want to do some more advanced things than just randomly link up a few mission chunks:

Show expected mission layout to the player before accepting it
Have optional blocks or choice between different blocks
Change mission layout during the mission: "the princess is in another castle" = add one more travel block and one enter + rescue block
Be able to increase variety later by adding additional objects like more location types
Be able to inject special story blocks into the dynamic missions that will always happen eventually

Part of the strategy element in the game is choosing which missions you accept so a lot of them will be discarded and there must be enough variation to make this choice meaningful. You might be badly equipped for forest encounters, but well equipped for sneaking into castles. And rescuing a princess is high-reward so the mission could be worth taking - this is the kind of decision I want the player to make.
I could probably just code this together in a way that works for now, randomizing a mission type, starting with the end block and work backwards from there to the start block. There will be some dependencies, like available location types depending on terrain type or available block types depending on the overall mission type. This seems like the hard part, figuring out what needs to depend on what and where to start from.
Other dependencies that come into play are:

Some missions types not becoming available until later in the story, easy to handle
Overworld location does not have much effect on the abstract "map" generated by a mission, except that some terrain types will be more common depending on where you are
Player may have access to various means of transport that will impact mainly the travel blocks
Factions exist and are somewhat tied to terrain, like elves in forest
If game world has a war between two faction I may want to spawn more combat missions against one or both of them depending on player allegiance

So do I generate elven enemies because I generated forest terrain first or do I change around my mission generation logic to look at target factions before terrain? (just an example of the kind of compromise I need to deal with).
Another model I considered but is not very keen on is having predefined fixed templates of missions to fill with blocks of appropriate types. I feel this could have me doing too much work the RNG could do for me instead and I might also have to consider template to mission type relationships.
My question is basically: Is there a strategy that would help me achieve this kind of mission generation in a relatively clean and maintainable way? A similar situation from your game that you can share lessons learned from?
Maybe there is not a perfect solution, but there are likely more or less good ways the problem can be approached in.
Game is a turn-based RPG/strategy game with OO design, but I don't think the details have a major impact for the concept I ask about. My object relationships are not set in stone yet. I think the dynamic mission-generation is a key factor in the game and if I find a good way to deal with that I may very well adapt other parts to work well with that model.

A:

I assume that your game world is already fixed and now you are generating missions which work in that game world.
First of all, you need to know which mission types are actually possible in the location you have. For example, your "Rescue" mission type template requires:

A location to gather intel
A location to infiltrate (the terrain to traverse is implied: It's whatever lies between quest hub and location)
An NPC to rescue
An enemy faction which opposes the mission

These are localized features which would be created when you design/generate the game world and then be more or less persistent. If you generate these features ad-hoc when generating missions, your game world will feel awfully inconsistent. It will be obvious that you create people, locations and factions out of nowhere which the player really should have noticed before just to never mention them again after the mission is over. The world will feel much more immersive if the player hears about the evil elves with their menacing castle and meets the beautiful princess before getting the mission to rescue her.
So when the player is in a location in the game world where not at least one of each of these components is nearby, then this particular type of mission is impossible to generate here.
So I would recommend you to implement each mission type as a Factory for Missions: a MissionFactory.
Each MissionFactory would have a method bool availableIn(worldLocation). That method would check the surrounding of that location to see if everything is present that's needed to generate a mission of that type. This is also the method where you check if certain political conditions are met (like your war mission example which would require two nearby factions which are currently at war with each other).
So if the player is in a quest hub and you want to generate a bunch of missions to pick from, you first need to filter your list of mission factories to those which are available in this quest hub by calling availableIn(player.location) and append those which return true to a list of available mission factories. Then when you want to create 10 missions, you take 10 random picks from that list (duplicates permitted) and call missionFactory.generateMissionAt(worldLocation) on each of it. 
Optionally, you could use weighted randomness. availableIn could return not just a bool but a number which says how probable  that mission is in this location. For example, "exterminate dangerous monster" might happen more often in rural areas while "assassinate political opponent" happens more often in urban areas, but each can still appear in the less likely location from time to time. 
The generateFrom method of each mission factory would then generate a random mission consisting of random features in that world location.

