For what it's worth, here's my take on "story" and advancement in 4e.I think this is a good description of what GMs do in RPGs in general--give the players something to want (or guide them in choosing it) and then put obstacles in their way (or bring new implications of the thing they want to light so they have to reconsider whether/how badly they want it). It makes sense to me how you do that with 4e but I like how a lot of that is "baked into" classic D&D in a certain form. The players want XP, which they get mostly by finding treasure. To get it they have to go through a dungeon, and the game includes rules for building dungeons (better in Basic than AD&D).
<snip>
The disadvantage, of course, of baking these things into the game, is that it's the same thing every time you play. You can give the PCs other goals and things to care about (and I do), but long stretches of the dungeon-crawl treasure-hunting game will reduce the focus on those things. I think if someone dislikes 4e because too much time is spent on combat rather than developing "the story", they would probably be even more frustrated in my game, because dungeons in my game do the same thing and take even longer to resolve.
PCs in 4e advance from heroic to epic tier. This has a mechanical dimension - XP lead to levels lead to power-ups that support the change in the story - as well as a story dimension. The necessary XP are earned for engaging the encounters that the GM frames. (This is a pretty big difference from classic D&D - you don't get XP just for taking your PC into the dungeon.)
So as long as the GM frames encounters that speak to that default story, earning XP equals developing the story. For instance, heroic PCs deal with goblins, but those goblins presage something about Bane and his role in the Dusk War. By the time the PCs reach epic tier, they are key players in the Dusk War (whether working with or againt Bane).
If the GM is using the default MM, then it's easy to frame encounters that are linked in this sort of way to the default "story" of 4e D&D.
I mostly stopped paying attention to the WotC modules after the early ones, but I think some of their weakness can be explained in terms of departures from the above: using monsters that have no link to the default story, so the enconters have no non-mechanical stakes or interest. Given how easy the game makes it to avoid this, it's kind of odd how badly they fell into this trap. (Just one example: in the module E1 they introduce a new primordial who has no prior standing in the 4e or broader D&D canon, and whom the players won't even learn the true story of until part way through the module. And then a good chunk of the encounters in the module are with the minions of this tractionless primordial.)
On this approach to 4e, I'm not sure about its replay value. There are multiple ways to play the game's default story, but they're probably not unlimited. 4e Dark Sun tries to put forward a different default, but I'm not sure there's 30 levels worth of material there. (I've often thought that if I were to run 4e Dark Sun I'd do it vignette-style, skipping by 2 or 3 levels at the end of each scenario.)