James at Grognardia has a great post on creativity and worldbuilding. In he relates a story about M.A.R. Barker the creator of Tekumal. Basically James got to talk to him and was relating the story of one the NPCs that James created for his campaign. The good professor surprises him by going "Oh I know this fellow" and supplies additional details that eerily fits well with James own ideas.
This is not unfamiliar to me in regards to the Majestic Wilderlands. The trick, for me, is to use fantastic realism. Aside from a few fantastic premises the foundations of the Majestic Wilderlands are the same as our history. Around 1990 or so the foundation of the Majestic Wilderlands came together pretty much in it's present form. From the premises I extrapolated everything else.
Of course it didn't came to me all at once. However what happened that from time to time I ran into an idea that that just seemed Majestic Wilderlandish. And so I incorporated it, adapting the idea to the specific circumstances of my setting. What make something Wilderlandish for me was whether it followed from the premises I laid out for the setting. The reast of the stuff mainly consisted reading a lot about history including trying to dig into how people thought and acted in various ages.
Also of equal importance was my players. The vast majority (including the current bunch) are good roleplayers and their actions and reactions helped to add many details to the setting. Even used some situations in various live-action events I ran (modified for the setting that the NERO Larp Chapter used). The results of that were interesting to say the least.
As remarkable as M.A.R Barker's genius is, it rests on a foundation that any of you can learn and adapt for your own setting. So while initially it may seem mysterious with a little time you can be spinning detailed tales of your own NPCs.