Modal thinking changed very slowly, over a matter of centuries, encrusted with tradition and conservatism but driven by the application of musica ficta. I can find songs of the 13th century which are clearly in a major mode, notably the famous "Sumer" canon, and for that matter some of the 12th century music of Hildegard von Bingen has sections that are major rather than following the theoretical church modes.
For broad brush strokes, I generally teach that church composers trained in the Northern European Renaissance style retained their modal way of thinking through the end of the 16th century and, for the more conservative, the beginning of the 17th, even if their secular music was already moving in different directions. Monteverdi is a key figure, knowing and using both the older and the newer musical styles with equal skill, but his music still does not fall under a clearcut non-modal definition. The historical beginning of the fully-realized major-minor system is generally identified with Corelli's first publications in the 1680s. The first serious attempt at theoretical explanation was made by Rameau in 1722.
John HowellMy own answer would be "sometime in the later 17th century, roughly around the time of Corelli (1680), or maybe a bit earlier with someone like Stradella (say 1660-1670)."
Of course, as someone attuned mostly to modal music (or at any rate to pre-key music, since the question of whether and how "mode" should be applied to medieval polyphony, for example, is an open one), I may tend to hear things in early 17th-century music as an expression of "modal fluidity," while someone oriented mainly to key-based music will hear the same music in terms of an "emerging key system."
Scholars such as Carl Dahlhaus have shown how music around 1600 (e.g. some of Monteverdi's and Gesualdo's madrigals) follow modal patterns. At least as important, I would say, they may follow rules of vertical progression different from those of the key system, whatever the mode or set of modes in use.
The difference between 16th-century practice or theory and key tonality is not just the scales used (Ionian looks identical to major, for example), but the different patterns of degree inflection (e.g. the fluidity of Bb/B in various modes), and patterns of vertical motion based on two-voice progressions coming down from Gothic practice, such as the expansion of a major third to a fifth or major sixth to an octave.
While I'm one of those people who finds the concept of mode helpful in analyzing Renaissance polyphony, I would emphasize that the patterns of vertical progression are equally important; 16th-century theorists such as Zarlino discuss these progressions.
Further, 16th-century treatises such as Zarlino's Institutes (1558) and Tomas de Santa Maria's Art of Playing Fantasia ("fantasia" meaning more or less "improvising at the keyboard, or on a polyphonic instrument such as the vihuela"), and 17th-century treatises in continuo, teach patterns of progressions from one four-voice sonority to another quite differently and (I would say) more fluidly than those of key harmony as codified by Rameau.
In "modality" (or whatever we choose to call the Renaissance and earlier 17th-century practice) there is freedom to emphasize various degrees of a scale, and also to mix octave species or modes, something discussed and recommended by Vicentino (1555). One cadences on various degrees of a scale or mode, using whatever accidentals may be appropriate.
Of course, some events and patterns are common to both systems, which leaves room for a lot of differing interpretations and debates. I might say: "In this piece in D Dorian, the composer often cadences on the third and fifth steps F and A, as Zarlino recommends." However, as I've seen in actual experience (when I recently shared some keyboard music from around 1600 with a friend who is a Baroque harpsichord enthusiast), someone oriented mainly to key-based music might quite likely say, "Isn't the composer modulating here from F major to D minor?"
I would ultimately say that the transition is located somewhere in the 17th century, but just where is another question (this is a bit like the When did the Renaissance start? question) Gesualdo and Giovanni Gabrieli and Frescobaldi seem modal to me, while by Corelli we're clearly in the key era.
We must still allow for the nature of musical change, which is neither instantaneous nor simultaneous in all areas. Thus there are pieces earlier than 1660 which can be analyzed using a key-based model, and pieces written after 1680 which can still fit a modal paradigm (Portuguese polyphony is one area which continued more or less in the 16th century fashion for some time afterward), which indeed Kirnberger (1771) continued to advocate for church music, and which he holds makes itself felt in some of Bach's music.
Margo SchulterFor a list of the medieval and Renaissance modes, see What were the twelve modes? discussion.