Ultimately, though, doesn't it amount to either the same thing, as the DM adjudicates what features are available? Either that or a contentious arms race that spoils the fun for everyone?
Potentially. The same thing can happen if a player takes longsword specialisation, or archery style, or whatever for his/her fighter and the GM rules that no longswords (or bows, or arrows) can be had for either love or money.
Or the wizard PC knows fireball, and the GM rules that there is no bat guano to be found anywhere in the land.
D&D tends not to have explicit rules, or even guidelines, on how the GM is meant to handle these issues where player abilities depend upon elements of the shared fiction over which the GM has the final say. (Though as [MENTION=59096]thecasualoblivion[/MENTION] notes, 4e is a bit of an exception here, with a more explicit orientation towards "say yes".)
My own view is that once a player has an ability like that, the GM is expected to allow it to come into play. A bit like thieves stealing the MU's spell book, I think a little bit of infiction action denial can go a long way. (In
this post, I give an example of when - as a consequence of adjudicating a skill challenge - a PC's familiar was temporarily shut down. At the time, this example prompted a
long discussion in another thread of when shutting down abilities via adjudication of the fiction is fair or unfair, when it is best seen as GM force or a consequence of what a player has staked, etc.)
I find it interesting how you are tying "player agency" to "impacting the fiction" mechanically, as opposed to just narratively. It's not exactly how I think about player agency, but it's certainly a valid way of thinking about it.
As I see it, there are two main ways that the players impact the fiction.
One way is that they declare an action, and the GM says yes - so the fiction changes in the appropriate way, and the game moves on. Sometimes the rules might oblige the GM to say yes - eg the player casts a Wall of Force spell, and so now the GM is obliged to allow that a wall of force has been brought into being - and sometimes this is up to the GM. In D&D, traditionally spells (and other magical effects) have been the main way to oblige the GM to say yes. But there have been other examples (eg the yakuza class in the original OA book has abilities around contacts and calling on clan assistance that come pretty close to this; and as has been discussed in this thread, there are 4e non-spell abilities that can do this).
The other way is that a player declares an action, and the GM calls for a check, and the check succeeds. In this case, the more resources the player can bring to bear (bonuses to checks; rerolls; etc) the more control the player has over the outcome. I personally find it fairly satisfying for the player to be able to expend resources roughly in proportion to the extent that they care about the outcome. (In 5e this might be via Inspiration, for instance; and you can then get a reward cycle going if the player can earn the inspiration back by declaring the action in the first place, because there is an alignment between what the player cares about and how the goals/flaws etc of the PC are framed.)
In your terminology, is the first way what you mean by "narratively" and the second what you mean by "mechanically"?
presumably the DM would give really high DCs to anything that might "spoil" his narrative.
Personally this is how I WANT my games to be run. I want the DM to be a storyteller, not just a referee. If I'm about to break the plot I want the DM to make it very hard for me to do so.
I'm mostly a GM rather than a player.
I play games that are pretty traditional in their basic allocation of roles to players and GM. (At the moment, I'm running 4e and BW.) As a GM, I have a large amount of control over the backstory, and an even larger amount of control over the practical framing of the ingame situations.
But I don't see myself as a "storyteller" at all, nor is there a "plot" to be broken. I expect the players to formulate their own goals for their PCs. I'll frame them into situations that put those goals into play, and under pressure: what the PCs do is up to them.
In mechanical terms, the main thing I therefore want is reliable guidelines for how much pressure I'm putting the PCs under - in practice, I think this is a function of (i) DC setting (and hp setting, for D&D combat), (ii) player resources and (iii) consequences of failure. 4e is pretty transparent on (i) and (ii), and as I run it is pretty forgiving on (iii) - which gives it a very heroic tone.
BW is pretty transparent on (ii), and encourages being pretty forgiving on (iii) - it is one of the original "fail forward" RPGs - but is much more brutal on (i): it encourages the GM to use "objective" DCs based on in fiction considerations rather than level-based/pacing-based DCs (like 4e, HeroQuest revised or Marvel Heroic RP). As a result it plays much more grittily and can be pretty tough on the players as their PCs get hammered over and over (but, because of (iii), are still in the game and still struggling towards their goals).
5e is pretty loose on (i) - of the other systems I've mentioned it's probably closest to BW - but also rather loose on (ii), especially out of combat and outside of the spell system. It's also pretty loose on (iii). In that last respect it could probably be tightened up into a "fail forward" system, though I think there may be other elements of the system that collide a bit with that (eg 5e seems to be based around fairly tight tracking of the ingame passage of time, whereas "fail forward" works best when that is something that is open to flexible narration by the GM - not a fatal problem, but one that a 5e GM might want to be aware of). But that would still leave (ii) - which gets back, I think, to some of the OP's issues about "randomness" and the balance of power between the GM and the players.