you don't want to throw the party against skill checks they can't make, knowledges they don't have, and the like.
That's not an issue in 4e - it has level-relative bounded accuracy.
I find I monster (for when the villains are monsters) that will fit based on their role in the world or what they're known for and add that to the story. And then I pray they're close to the right level/challenge.
What I had in mind was - when you introduce an NPC or monster into your gameworld, how do you know that s/he is a villain?
In my game, that's generally a decision for the players to make, in the playing of their PCs.
Let's look at White Plume Mountain for a second. There's a big room full of boiling mud, a room that's a spinning cylinder, a room that's under hot spring, and a frictionless room. And so many others. Rooms were interesting because monsters were boring.
If WPM is the standard for "story and imagination", then I will put
this up against it: caverns rather than rooms, but not uninteresting. Or
this: I wouldn't really describe the Soul Abattoir as a room, but as a location it was memorable.
I've never played KotS, but I thought its most interesting location was the one with the portal. The WotC 4e module that I know best is H2. It has a room that is a pool of blood with an animating statue in the middle, another room with various teleporting and trapping mirrors, a room with a giant pit that a dragon flies out of, etc. Plus the kitchen/dining room in the chamber of eyes has all the usual furnishing, stores etc.
The rooms don't need to be interesting or memorable because the fights are. The gameplay is fun. So that becomes a crutch and all the fun rests on the gameplay and not the imagination.
I don't understand why imagining scenery is superior to imagining characters. "The Phantom Menace" has more elaborate scenery than "My Dinner With Andre", but I think by just about any measure the latter is a superior film.
Despite their many and evident flaws as written, I think The Bastion of Broken Souls, or OA7 Test of the Samuari, are both more interesting scenarios than White Plume Mountain. I got about 2 years of play each out of the premises of those modules: the latter a fallen demigod trying to turn the world's air into a poison that he will be able to breath and thereby regain his immortality; the former about the fate of the souls of the world, suffering as a result of an ancient pact by the gods that seemed like a good idea at the time. I can't remember any scenery from Bastion of Broken Souls (other than the positive planar stuff that I didn't use); from OA7 I remember the underground, water-filled caverns of the snake cult (because the PCs had a reaosonably dramatic fight there) and also the Momoben Forest where the Peachling Girl lived (the PCs rode through the forest on the backs of great tigers).
In both cases, though, I remember characters - the banished god in Bastion of Broken Souls, whom the PCs befriended; the angel who had to die to open the gate to said god, whom one PC persuaded to let herself be killed, breaking her obligation so as to honour the higher values she was called upon to serve; the dream sorcerer and night hag whose backstory as written I can't remember, but in my game was a secret child of a former Lord of Karma, with great insights into the dreams of all living beings. And in OA7 I remember the Peachling Girl, Za Jikku the fallen demigod, the somewhat hapless peasant monk (Setsu Ikki?) who was the plot device around whom events turned, plus the various NPCs and PCs from my own campaign world who got bound up in the whole thing.
For me, character is not a "crutch"; it is of the essence of story and imagination.
Encounters are only memorable when things are outside the norm: lucky crits, dramatic reversals, improbably strings of luck, etc. I.e. when the rules are not behaving as normal.
This is another case where you speak in the third person when I think you really mean to be speaking in the first person. You seem to be talking here about what makes encounters memorable
for you. For me, encounters are memorable because of what was at stake, and who was confronted.
Here are a handful of those that I've written up as actual play posts. None of those turned on lucky crits or improbable strings of luck. (There was the odd dramatic reversal, but in 4e that is not the rules not behaving as normal - the whole point of the 4e action resolution mechanics is to produce dramatic reversals.)
Of these four examples, only one - the last - involves scenery (an earthmote from which Vecna fell with the paladin falling after him Gandalf-style; and the Red Grove where the PCs bound a demon to their service). I think the first remains probably the most satisfying social scenario that I have GMed, and the second still stands out to me as one of the tighter moral crunches into which my players have ever got themselves.
The catch is, as much as the rules hinder my ability as a GM to make up outcomes, they also hamper the players'. The rules are equally restrictive on what we can or cannot do.
To be honest, as I said upthread, you need better rules. The links I've posted above are only to a portion of the episodes of play I've written up on these boards, but they contain illustrations of the players making choices that are as imaginative as any I've seen in multiple decades of RPGing. 4e is not the most flexible system I know of (I would probably give that label to HeroWars/Quest, though I imagine there are Fate diehards who would contest that). But it is certainly the most flexible version of D&D, or any other remotely trad FRPG, that I know.
It's certainly far more flexible in play than AD&D, for instance.
If you're only playing The Mechanics, if there's no narrative overlay apart from perhaps talking in story, there is less substance. There are fewer layers. By definition there is less going on.
Can you still have fun? Yes, of course you can. Is it wrong? Nope. But there's less going on.
It's genuinely refrehsing when someone is candid. I respect that. But I have a lot of actual play posts on these boards. I've linked to some of them above, and can provide more links if you like. I may be wrong, but I really believe you have no conception of the sort of game I'm running.