Actually, depends on the NPC role.
No DM lacks for powerful NPCs if such a role is warranted, adding a powerful NPC is a mid-game addition, depending on the sort. You can have a former adventurer rise to power(such things take under a year), a sealed evil awoken(such things only need someone foolish enough to unseal it or for a seal to unseal), arrive from another part of the world(planar in a low power setting, other continent if theres a Continent of Uberness or badass Underdark) or was created(someone makes a breakthrough that Should Not Be somewhere).
Say a Lord of Dust was awoken when the Mournland was created, and finally broke loose fully in Year -2 Circa Adventurers. Adventurers were involved when, 2 years after his release, he invades Aundaire with a legion of freed minions and takes half the country before they managed to rally a defense.
Removing an interfering NPC requires more work, as each such NPC has interests and territories they impact. The higher level they are, the wider the impact.
Say you need the Lolipope to not be present so that your PCs can wreck the power structure of Thrane. So she goes missing. Thrane is thus greatly weakened, and a theocratic uproar ensues.
This is a bad example mind you, as Jaela cannot leave her place and thus has minor impact.
So lets hypothesize, a ruler of Sharn who raised the city singlehandedly with one spell. His roles are to A) keep the city up by keeping the planar bleed JUST thin enough to allow levitating buildings but not thin enough for planars to rush in B)kick the ass of planars on the other side as they mess with the bleed C) rule Sharn D) annihilate things that threaten the structure of Sharn.
So now your PCs are going to do something like try to conquer the city. This would not work with Hypothetical Wizard Ruler, so hes going to suffer an accident. The angels on the other side has had enough and kidnapped him in force. Now the PCs are free to conquer the city....no wait, the city is about to fall, because the planar bleed is closing, the Houses, now that theres an opening for a leadership position fight for power, enemies of Sharn egg them all on, and drum up the forces to conquer the place, because they couldn't get close enough before said Wizard unleashes Slay Army spells.
See the difference?