e: The thing is though, there's two camps here. One that thinks that a story should merely be a vessel to take us to the gameplay and nothing more and one that thinks that a good, interesting story intertwined with good gameplay makes a great game.
I don't think there are two camps here. I'm perfectly happy with either of those. The trouble is, most games that think they have a good, interesting story to tell don't - the standard of writing in videogames is typically very low - and when a game thinks it has a good, interesting story to tell and doesn't, you've just taken a wrong turning at Exposition Junction and are en route to Wordopolis. Even when a game _does_ genuinely have a good story, it's easy to let endless cutscene syndrome sneak up on you - the player's there to play a game, and if they wanted to watch a movie, they'd probably have rented a movie.
A minimal story is safer; if it's lousy, at least you won't waste much time reading it, and it can _be_ corny because it serves another purpose. Dwarf Fortress's little bit of chat "... Strike the earth!" puts us stock in generic fantasy, but that's OK - we're released to play the game almost immediately. Deus Ex puts us equally stock in "collect the whole set" conspiracy theory territory, but it won't shut up about it; by the midpoint of the game, the only surprise might be if the Illuminati _don't_ turn up.
A fleshed-out story also risks serious cognitive dissonance with the actual gameplay. The classic example there is surely FF7 (I'm not even going near the question of whether FF7 has a good story); even though we've seen Aerith bludgeoned, shot, shivved, bit and burned in three hundred random encounters across half a continent, she gets stabbed by Sephiroth [1] and wham, she's dead. All very moving, or it would be if it wasn't for the little voice in the back of your head going "Ah, a Phoenix Down will sort that out in no time."
And do we get that in Deus Ex? You betcha. Even though Denton is one of UNATCO's top agents, the absolute best of the best, it doesn't take long before we find out that he is laughably incompetent at everything (furthermore, if we were paying attention during the tutorial, we know that UNATCO could make him awe-inspiringly competent, but choose not to) thanks to the much-vaunted CRPG elements. Not only that, it turns out that their top agent can only receive ammunition and supplies by wheedling with a man who is rather reminiscent of your boss's secretary guarding the last paperclip in the stationery cupboard - and, incidentally, if they wanted to make the least surprising plot twist in gaming actually have some consequences, a sudden transition from being allowed all the equipment you can carry to having to manage your supplies carefully could actually have been quite interesting.
And there's another clash between story and gameplay. The game mechanics encourage you to investigate every nook and cranny picking up multitools and lockpicks like some kind of demented magpie. Now, that's a fun thing to do, exploring everywhere - but the contrast with the plot, which often establishes a sense of urgency to our objectives, is somewhat jarring. If we're trapped in an MJ12 facility trying desperately to escape, just _why_ are we looking under every rock in the hope of finding a sandwich?
Of course, the other thing Deus Ex is praised for is the choice of approaches - charge in like a demented gun-bunny, sneak in, hack stuff, whatever. But there are two issues here. One is that none of those approaches is done particularly well. The shooting isn't as good as a straight-up FPS from the era; the sneaking isn't a patch on Thief (in particular the way that when a guard is alerted by anything they immediately make a beeline straight for your position which they have apparently psychically intuited is quite vexing); the hacking game is barely extant, and so on. Sure, we have a choice of mediocre gameplay, but it's still mediocre gameplay.
The other, more serious issue, is that the "figure this out using whatever tools you have in your box" game is hard to do without procedural content. We know, in Deus Ex, that there will always be a way to come charging in, guns blazing; there will always be a ventilation shaft between secure and not-secure; there will always be a password on a blue post-it note under a desk, a convenient sniper vantage, a handily positioned security control computer. Furthermore, since we're in modern-FPS save-and-reload land, we find ourselves heavily drawn towards prior-knowledge attacks (where we use something we shouldn't really know at that point in the game, like the layout of the terrain ahead), something the system of bioelectric energy heavily encourages - sure, you can be awesome, but only for twenty seconds, and knowing when the _right_ twenty seconds is is a powerful weapon.
That kind of thing can work in a roguelike. There's no guarantee that every approach will work, and you're got to figure out which approach to take in advance because there's no doing it over again. But in Deus Ex, you know for sure your preferred approach will work, which ain't much of a tactical decision.
[1] After thirteen years I think we may dispense with spoiler warnings.