The way I see it, if you're going to tell an interactive story well, the mechanics must harmonize with the narrative. There are two approaches to this that immediately jump out at me.
One is to craft the narrative space, block out the actions required of the controllable characters in order to navigate that space (or the actions possible in the space), and design mechanics in order to allow those actions to occur. I hereby name this narrative-first design.
The other is to come up with a set of interesting/fun actions, then design a narrative space for which they make sense. I hereby name this mechanic-first design.
Now most projects probably switch back and forth between the two modes of design depending on the current needs of the project, the stage of completion, and the whims of the executive producer. But for argument's sake I'm going to list a couple of examples that I think fall clearly into one or the other camps.
Dwarf Fortress takes the approach, since it's only display mode is ASCII, of using all the processing power not used for fancy graphics to simulate a complex series of interlocking systems that make up its world. The open-world free-form approach allows for a variety of highly entertaining (and often retold over internet forums) narratives to occur, all because the basic simulations are interesting and solid. I would call this mechanic-first design. The counter-argument is that (I'm making this up here, since it is nearly impossible to know designer's intent from finished products) the creator had in mind at least the basic game premise, a fantasy world in which you control a colony of dwarves who build things, which in turn restricts already the possible simulations and narrative spaces. But I'd say it's at least 70-30 mechanic-first.
Inform 7 is a text adventure engine. It essentially provides, along with a bunch of free downloadable modules, a basic interactive framework of real-world-ish systems on which to craft your narrative. Doors open and close, rooms are moved through, objects go inside containers, people move around, etc. The point of this system, it seems to me, is to allow for easy narrative-first design, which makes perfect sense in the context of the interactive fiction genre. I would argue, also, that most of the graphical and text adventure genre have been designed in a narrative-first manner.
When thinking about your personal or collective (if a company/team) design process, what type of design strategy is followed and when? How much importance does the flavor, atmosphere, genre, story have in dictating mechanics and vice versa?