Yeah, but now that we have the ingenuity of Wiley Coyote, Tom, and Jerry behind the game, I think we're in a different place. Anything is possible with some rope and an anvil!
But seriously, the examples you give just show that it IS possible to add more variation into quests and I just can't believe that it would detract much from performance. Seems to me, it would simple add a bit to processing demand during the 2 seconds in which a new dungeon instance is being created. Not saying I fully understand the Turbine game engine, but I've programmed since the mid-90s and just can't imagine that an elegant solution isn't possible.