May as well throw my hat in here.
As much as I love me a good story, I think this sort of question misses the point a little.
It goes back to that trifecta comment and having to achieve two of the three for a game to grab us, but personally, it goes deeper than that.
And that deeper question is whether the dev team has a cohesive vision of what their game is suppose to be, followed by how closely the game they make manages to achieve that vision.
A vision is more than an idea, a story, the mechanics, or other aesthetics. It's how the game is suppose to feel when you're playing it, and if the team is able to grab onto that vision, they are more willing and able to fix the initial design flaws, are better able to reach into their artistic soul and create assets that evoke that feeling, can better know how this little piece they're coding is suppose to fit into the greater whole.
The other trick is to have the right team with the right timeline to pull it off.
For a long time, my shorthand was to say that such games had a soul (that I connected to), but I think it's closer to say I connected to the vision the team had and managed to implement.
Because I really connected to the vision the Mega Man X4 team had for the Zero character for that particular go at the series, and the story was rubbish, the music only good, and graphics solid to great but not especially inspiring. The reason is that they aced the feel of the character, they managed to evoke the exact experience they were hoping for in me. For Mega Man X4's Zero, it was mostly mechanics, sure, but a bit of everything else too.
In Bastion, it was the story of the Calamity and those it effected, as conveyed by the Narrator, other audio/visual aesthetics, and supported by solid gameplay with one moment of genius.
In StarCraft, it was Kerrigan and everything surrounding her.
In Chrono Trigger, it was the cast of characters supported by pretty much every aspect of the game.