Felix said:
DM Fiat allows DM's to say, "I have a reason for this, so quit second guessing the NPC's ability to do X, which you think he shouldn't be able to do, and move on. Jones, it's your character's initiative; what do you do?" It protects the game from belligerent players.
Okay, I think we're zeroing in on the disconnect here. To use an analogy to a CCG, I don't really think of the DM's privilege as the only member of the table to play with his cards in his hand, rather than on the table, to be an example of DM fiat. I would consider DM fiat to be if the DM were to be altering his cards depending on what he saw in the players' hands, if he didn't like the way things were looking to go.
The reason you don't second-guess the DM is because you trust him not to be altering his cards, because you believe he's playing by the rules. If the DM is exercising fiat, you don't know whether he's playing by the rules or not, and may be justified in second-guessing him.
The DM has an advantage over the players because he can conceal his hand while observing the players' hands. This is a necessary part of the game. Otherwise, the DM could never surprise or confound the players and the whole thing would just turn into a die-rolling exercise. However, along with this advantage comes the temptation to swap the cards in his hand for other cards, pulling out the "whoops, he's immune to your acid" card or the "I know you rolled a 35, but Diplomacy doesn't seem to work with this guy" card whenever he wants to. If you know your DM does not exercise fiat, you know that he drew those cards fair and square.
To break from the analogy, in other words, those characters have good reasons for being unaffected by your spells, skills, or whatever, and if you were to ask the DM to show you those reasons, you would see that they are playing by the rules.
Essentially, the way I read it, DM fiat is when you break from the ability to honestly show your DM's notes to a player for checking. Not that I think any DM should have to. But an indepenent observer should be able to ask you the question "why didn't his diplomacy check work," and get an answer that would satisfy a reasonable player.