Monster statistics aren't secret backstory. They're not backstory at all.
A fictional fact about a monster (eg death knights never flee in terror) is backstory, but is it secret? From whom? Not anyone who's read the Monster Manual. In 4e, not from anyone who makes a Monster Knowledge check. This goes to [MENTION=99817]chaochou[/MENTION]'s point about conflation.
I don't think your notion of saying No is coherent.
If a player makes a roll to hit, and the roll is a failure, the GM (in a system that has such a role of the more-or-less traditional sort - all the RPGs I play do so) will tell the player that the attack failed. No one on this thread has suggested that that is "Mother may I." It's a failed check.
If a player engages in a contested check against the GM rolling from some NPC's stats, the check may fail. And the player may not know in advance what the chance of failure is (depending on game rules and table conventions about keeping GM-side stats secret). If the NPC's stat correlates to the fiction as presented by the GM, this will almost certainly not be characterised by anyone on this thread as "Mother may I." If the NPC's stat is a rabbit from a hat, then maybe it is closer to that, though.
If a player declares an attack with a fear effect against a death knight, and fails, is the player allowed a retry? In most approaches to GMing D&D, the answer is yes (perhaps at the cost of some hp loss due to the Death Knight getting in an extra round of actions, having suffered no hp loss itself due to the failed effect). That's already different from the tea house case, where there is no systematic framework for retries. (We try the teahouse. We try the docks. We try the guardhouse. Etc. That's not retries, that seems like the very paradigm of fishing around for an answer from the GM.)
Does the player know that the attack may fail? If the fiction has been well-narrated (eg undead lack mortal minds) then perhaps. Is the aim of play for the player to solve the puzzle of how to defeat a death knight (like the demi-lich in ToH)? Then perhaps we are in "Mother may I" territory, depending on further details about whether it was a puzzle the players were expected to reason out, or a flat-out guessing game.
Notice that in the 4e DMG example of a Duke who can't be intimidated, (1) there are retries permitted within the framework of the skill challenge (until the 3rd failure occurs), and (2) the information is accessible within the scene, as the outcome of an Insight check (ie an attempt to learn further fiction about the personality/disposition of the Duke).
The various distinctions that I have drawn above may not be interesting or significant to you - I don't know. I think most RPGers who are disinclined to approach resolution through the GM decides approach are likely to find them significant.
If you point to certain GMing practices (deploying monsters with unanticipated immunities as a trick/test for the players) in the context of a particular RPG that is not well-known for its support of non-GM decides play (D&D in its non-4e versions), then I'm not sure what sort of test you are engaging in. Perhaps all you're doing is showing how hard it can be to play D&D in a non-"Mother may I style", because (outside of its 4e version) it doesn't provide robust mechanics for allowing framing to unfold within a scene in a way that is dramatically and narratively satisfying without risking a total hosing of the players (the demi-lich in ToH would be a poster-child example of the absence of such robust mechanics).
After all, I would conjecture that many of the posters who don't care for GM decides in the teahouse case wouldn't be very keen on monster with unanticipated immunity as a trap/test for the p layers either. (I'm not, for instance.) It may not be a coincidence that, of D&D editions, many of those posters seem to prefer 4e, which does have robust mechanics for handling this that other versions of D&D tend to lack.
Anyway, turning to RPGs other than D&D: upthread there were discussions about how new backstory might be introduced in DW by way of moves like Discern Realities or Spout Lore. How would you see your Death Knight example working out in that context? Learning that the Death Knight is immune to one of a PCs' main forms of attack might be a "soft" GM move.
In my Cortex+ Fantasy game, the players learned that a Crypt Thing can teleport people away from it when I spent 2d12 to end the scene, and described their PCs being teleported away to some place deep in the dungeon. The fiction was new to them, but the spend 2d12 to end the scene mechanic is a core rule that they were quite familiar with. A novel immunity would also rest on a core mechanic (spend a Doom Pool die to activate a SFX that permits disregarding Stress, Trauma and Complications having a certain sort of in-fiction origin or character).
Of the non-D&D fantasy systems that I am familiar with the one that comes closest to D&D in its GM builds monsters and sometimes keeps details of them secret from player is Burning Wheel. But there are other features of BW GMing principles and techniques that would mean that immunities, if unrevealed, are unlikely to be unanticipated. For instance: when, in my BW game, the PCs fought zombies, the zombies had a high degree of crit reduction which made them hard to maim and kill. One of the players commented that it felt like fighting zombies. Those "resistances" were not revealed in advance of play, but were not unanticipated. Confrontations in BW (be they martial or social) tend to be deeply grounded in an unfolding fiction very differently from D&D (even 4e), which makes the idea of We just came across a death knight, and fought it, and found it immune to our Fear effects largely inapposite.
This is what underpins [MENTION=99817]chaochou[/MENTION]'s request that you identify some games, other than D&D, that you have in mind, when presenting your example of how combat might be framed and adjudicated and are suggesting that it is no different from the teahouse example. (Note that, if the absence of the sect members from the teahouse was deeply grounded in an unfolding fiction then it becomes much less likely that the example actually occurs, as it becomes much less likely that the players would just declare We go to the teahouse to see if any sect members are there and then look to the GM for an answer.)
What's the trouble? I assert (1) that many tables play Dungeon World and other PbtA games, and (2) that at those tables fudging doesn't occur. Likewise for Cortex+ Heroic. And just to add: fudging in Cortex+ Heroic, played by the rules, is literally impossible because every player at the table can see the dice pools, see the results, and keep track of whether any stress or complication has grown beyond d12 in size (there are no hp totals, secret or otherwise).
Fudging is also impossible in Cthulhu Dark - the only time the GM might roll the dice is to set up a contest for a player's check, and the result of the die roll will be visible on the table where the die has landed. And the only numerical stat that is tracked is Insanity, which is recorded on a die sitting in front of each player. That said, there may not be many tables playing Cthulhu Dark, although that would be a pity as it is a good RPG.
