Dungeon of the Mad Mage is full of different stories. Unfortunately, you have to puzzle them together yourself. That is mostly due to the way the book is structured: For example the chapter my group is currently in, level 3, has 1 page of background narrative, and 15 pages of room by room descriptions. Thus if you want to know everything about, let's say, the Legion of Azrok, you'll find only the basic information at the start of the chapter, and you need to piece together the rest by reading through all the room descriptions in which the Legion of Azrok is either present, or mentioned.

The other problem with a mega-dungeons is that players will take a lot of "left or right?" type of decisions. As most of the time they have no idea what the consequences are of going left rather than right, this ends up with them taking a more or less random path through the level. Which means that they can easily end up encountering different story elements in a different order. Some of which make more sense than others. The classic example is meeting a quest-giver only after encountering the target of the quest. Depending on the quest, they might either have already done what the quest-giver was going to ask them to do, or they might even have made it already impossible to fulfill it. "Please go and save my pet goat from the orcs!" - "Hmmmmh, maybe we shouldn't have butchered and eaten that goat we found when we killed the orcs."

The solution for the dungeon master is making things up. Sometimes you just have to move things from a corner that the players ignored back onto their path, because that is the clue or story element they need for the story to make any sense. And sometimes you just throw out the pre-written story because it has gotten too messed up, and invent a different one. Or you just add a new story, because players did something that gives you an idea for a story. It would be great if the adventure module were of more help, but if that isn't the case, you just need to be more creative!