I think mostly what I'm saying is that fiction operates on a very different dynamic that doesn't really apply to D&D from a strict rules perspective - in what I consider to be good writing magic serves the narrative, rather than being a tool for resolution, or else it becomes deus ex machina and the struggles of the protagonist lose meaning. This form of serving the narrative then changes the nature of challenges. For example, if a hero can zap a lock with magic, then the lock of the prison is no longer an obstacle - instead the narrative changes to a story about sneaking out. Of course if the hero can just teleport out then there really is no obstacle at all, so then the event needs to serve some other purpose. Does he overhear something? Meet a new ally?
So along the lines of the Chekhov's gun principle (
Chekhov's gun - Wikipedia, the free encyclopedia) - every scene should serve a purpose. Why is the character there doing what he is doing and how does it further the plot? Magic can dramatically re-frame this question.
The more I think of it, however, this line of thinking might be very useful for understanding what's going on though - For example, this is part of why magic using characters can run rampant in older D&D editions. They can reframe the challenges and encounters to a large extent with narrative changing abilities like scrying, teleportation, and raising the dead, while the non-magic users can't.
In fiction, while magic capable characters get these meta-narrative shaping traits, the non-magic characters are often given all of the coolest traits that define the conflict (like heir to a lost throne, for example). This keeps them relevant and goes along with my point earlier that often protagonists are mundane while the facilitators are magical.
In D&D there is no such compensation. Of course you can always make it work that way if you want, ala what Plane Sailing suggests - but that requires a set of skills and motivations that aren't really in the books, and operate outside of the system. Narrative style mechanics could capture this kind of player balance, but then I suspect that you're looking at a type of game that D&D is not trying to be (even if you can make it work). For example, there are many games where you can have more plot-oriented stats such as "incorruptible," "heir to a lost throne," or "soul-bound to a fallen angel," instead of ability stats. In those kind of games, balance between players operates in very different ways (with their own sets of problems as well).
4th edition D&D helped to address this problem by simply toning down or removing the meta-narrative controlling powers from magic characters. I think that really watered down a lot of the open and creative feel to the game though. I wonder if there is a different way to address this by giving a very different sort of narrative controlling power to non-magic characters.
EDIT: Of course then you're really messing with the core "story" of D&D, which at heart has always been about kicking down the door, kicking the monsters in the junk, and taking their stuff.
EDIT: A quick idea I just had: Protagonists define the conflict, while magic reframes it.