The discovery I'm referring to is not that variety. Rather, it's where the DM knows what's going on behind the scenes but the players don't, and they have to suss it out (or not).
I'm just going off of the earlier example in the thread, which was an illusionist who had framed a prince. If you have the player design that illusionist, all sense of discovery (with respect to how I have explained I am using the term) is lost.
If the NPC is just a minor bit NPC, I don't think it really matters. Sure, the player might be a little more engaged seeing someone they imagined. On the other hand, it'd probably be less work for me to do it myself. I can just improvise an unimportant NPC on the spot (though I recognize that might not be the case for all GMs). The only real work there is jotting down sufficient notes so that if the NPC reoccurs, they are consistent.
I don't think it's necessarily true that the GM knows what's going on behind the scenes, even in D&D (although it's much less likely here). You can play in a sense that everything's on the table and you'll find out what happens through play. This is a case where the play moves the fiction.
To touch on an oft-used example: a PC is outside the walls of a keep they want to get into, and says, "hey, I think I remember a story about the builders of this castle having a secret door for escaping it that supposedly comes out around here. I'm going to search the wall to find that secret door." Now, the important thing about this is that none of this has been previously established in the game -- neither in play or in the GM's notes (which typically don't even exist in this style of play except as a log of play outcomes). But, this statement can be tested by the games mechanics -- even in D&D. The GM calls for a check, the stakes are negotiated (by whatever the game/table uses), and the check is rolled. On a success, the PC does find a secret door -- it exists after all! On a failure, the GM complicates the situation to the detriment of the PC's goals. That can be pretty broad, in this case, as the PC goal was to gain entry to the castle, finding a secret door was just the method. The GM could frustrate the method and say no such door exists, or you find where one was but it's been collapsed/sealed or the GM could add badness by saying you find a door, but when you open it it's guarded! Or, while searching, a guard patrol rounds the corner and challenges you! The GM could establish that a door exists, but complication, a door doesn't exist, or even that the existence of a door is still unknown but you have to deal with this new problem before you could pursue it further.
In this style of play, the GM doesn't know anything more than the players. Everyone's playing to find out. This is, largely, how Powered by the Apocalypse games work. The GM can prep complications, or think of ideas before play, but they need to hold on lightly as the game can quickly move well outside of any such prep. It's not useful to do much work here. Further, the GM's job isn't to spur on players -- they frame a scene that has a complication and then follow the player's lead, only adding complications as the mechanics call for them. Adjudication of action is simpler, but you're the bringer of bad neww.
Now, I'll agree this is difficult to do in D&D. It's hard to run a D&D game zero prep because of how detailed and swingy the combat sections of the game are. You usually have to do some work, or have done that work for a time to be good enough to do it on the fly and not break things. But, you can do it in the exploration and social pillars to a great degree. I often prep social/exploration challenges as just a list of interesting complications/adds and some motivations so I can react with a bit of forethought. Takes a few minutes, and, honestly, I usually end up doing it on the fly as the players present things I hadn't considered before. The minimal prep does aid in setting up a pattern for me to fall back on, but that's really all you need. Skill challenges in 5e work very well with this so long as you don't script them.
An example of the skill challenge social pillar in this style for 5e: I had two PCs that were investigating a rumor they had heard about one of the PC's background NPCs -- a nemesis to that PC. They started by taking the hook I had thrown that there was someone at the Forge (a location in Sigil) that had been overheard talking about the NPC. So, the PCs went there. I started a 6/3 skill challenge for this -- 3 failures meant that they would not succeed at their goal of finding information -- what that looked like I left open to see where the fiction was at that point. 6 successes meant they would find information -- what that was I left open pending the ratio of success/failures. Each failure would complicate the situation, each success improve it. So, they went to the forge and succeeded at a task to ask around and find the person who had been overheard: 1/0. They then failed at an attempt to persuade the person to talk about the NPC. 1/1. This meant I complicated the situation, which I did by deciding this person didn't actually have the information they sought, but might know who did depending on future challenges. The PCs then successfully intimidated the person, so they revealed that they didn't know much more than was already related by the rumor, but that someone called the Butcher did and told them where he usually was. 2/1. I deployed the previous failure and moved them forward.
They went to meet the Butcher, who was described as a huge half-demon actually wearing a butcher's apron and with a massive cleaver at his side, sitting in a disreputable pub. Diablo fans may notice the similarities. One PC immediately attempted to intimidate the Butcher, I suppose since that worked last time. It didn't work here, and the PCs noticed that everyone else in the bar had stood up to stand with the Butcher. 2/2, with failure causing an imminent threat of violence they were ill prepared to deal with. The other PC used persuasion to settle the situation down and succeeded, 3/2. They then used perception to look to see if there was anything useful about the Butcher or bar they could use to negotiate. That success (4/2) lead to noticing that there were a number of plaques on the wall thanking the Butcher for community service and that the seat the Butcher occupied at the bar looked to be handsomely custom made for his size, a clear sign of favor. Not wanted to guess, the PC then using Insight to try to suss out if the Butcher really was a nice person that this community loved or if they had scared the local population into giving false accolades. The PC hoped it was the former, so on when they succeeded, it was, indeed the former -- the Butcher was a nice guy fiercely protective of the local community. 5/2. The PCs then deployed this knowledge to gain advantage on a persuasion check by framing getting information on the NPC they sought as a way to help the community by dealing with a danger. They succeeded, 6/2 and the Butcher gave them information. However, since the did almost fail, I tempered that info to say that the NPC had left town, but that there were lackeys still here, which gave the PCs a win in that they could directly harm the NPC's organization and get better intel on what that NPC was up to.
None of that was scripted or thought out before play. I used the themes of Sigil (which I don't own any setting material on and only read a few entries online to get the overview of -- and a map) to push play from my end on failures, but the bulk of the direction of that scene was the PC's. If they succeeded, the fictional framing moved in their favor, usually according to their wants. If they failed, it moved away from where they wanted it. I really only had input on failures, and that constrained by the player goals. The rest was reacting to what they did by calling for checks.
