I find that inspiration strikes me in the form of "Moments"- kind of like snapshots of what a game should be and the reactions it should elicit from the player having the experience. Like Shadow of the Colossus' moment would be delivering the killing blow to a giant beast while hanging on for dear life- the feeling of victory against insurmountable odds, coupled with a constant acute fear of being thrown off and having to start over. The whole game is built off of those moments. I'm sure that the story was written to facilitate getting to have those experiences.

Sometimes the story is as much a part of those fundamental moments as the gameplay itself. for instance, none of Chrono Trigger's "Moments" are inside of a battle sequence. instead, they usually directly follow one. The feeling of wiping out an enemy with Luminare is totally trumped by that time when Chrono sacrifices himself in the battle with Lavos, or the face-off between Frog and Magus, or when Robo gets himself trashed by his own Robot friends. Those are story driven Moments- the gameplay serves to break up the plot, and uses the next chunk of plot as a reward for beating a boss or making it through a dungeon.

I've heard that music bands often have hundreds of song progressions without lyrics, and similarly hundreds of lyrics without song progressions. The lyricist might write words for a particular music track that he has in mind, or he might write something he feels is really compelling and spend time working out an appropriate track to put the words to.

Sometimes production works forward, sometimes it works backwards.

I personally find everyone's opinion as very instructive. In fact, I must say that all the members has got its very good deal of reason and that if there is an absolute answer to the complexity of having to choose between story or mechanics, no doubt it will be a mid term between all these contributions.
If I had to be more explicit, both options complement each other, as the mechanics can grow up from a slightly more mature story and vice versa.

I was eating lunch with a friend today and they mentioned that most game companies create a game first and do the story last. I, however, am a strong advocate for creation of story first. Preferably before even one line of code is written. So a question for those who have done it. Does your company write the story first when tossing around an idea for a new game (even just a rough draft) or do they do the story last, and why?

Ah, the question of top-down design...

By "default", story comes last primarily because the focus is set on gameplay, and a story is created to fit that.

That being said, there are a number of reasons why you might want to have story first (top-down design).

Reasons I can think from the top of my head:

- In Magic The Gathering, the development team chose to do something bold for one of their sets (Innistrad I believe?) where they simply decided to start with the story and design mechanics based on that.

- Some games are deliberately more interactive stories than games, and require top-down design to work. A lot of modern AAAs, for example, are inherently top-down, though certainly not all. Assassin's Creed, for example, hinges a lot more on story than Batman: Arkham City (I need to update my references, sorry!)

- Brand management: when a game gets developed for pre-existing media (a tv series for example) you already have very rich content to draw from (story-wise). It's generally easier and more desirable to draw from this content.

- "Reskin": Using pre-existing game mechanics and reskinning can be a boring process, but to make a more "fun" game, it's best to start with the game's story and re-implement the core mechanics of the targeted proven gameplay (thus reducing "fun factor" risks).

All in all, story or game first depends entirely on the mindset behind the project being undertaken.