The brief answer is that there were basically always F-sharps, which dated even before it was standard to call that note of the scale "F" in all octaves. (The practice of repeating the letter A with each octave, rather than simply continuing past G to H, etc. through the rest of the alphabet became standard at some point in the 11th century.) Vertical tritones would pretty much never have been acceptable, and they were one of the first adjustments ever discussed in music treatises from the moment that harmonization of chant even became a topic.
To discuss this in more depth:
Plainchant doesn't use it, as far as I know, with Bb's being the only
non-natural pitch.
There's a lot to unpack and explain here. First, it's important to note that plainchant existed before modern (or even medieval) staff notation. And it was an oral tradition before the imposition of the standard gamut happened between the 8th and 10th centuries. The standard gamut was a synthesis of Greek scales, and the reason it allowed B-flat was actually due to a synthesis of two Greek scales basically into one "gamut" that became the standard scale system. Originally, that B-flat was only allowed in one particular octave as well (essentially on the B right below middle-C in our modern notation). B-flats were not allowed in other octaves: again, this had to do with the original Greek scalar construction that was inherited and imposed on a pre-existing oral chant repertoire. (I'm not going to explain the details of the Greek scales and why B-flat and B-natural both existed; just take my word for it that it's a theoretical construction that generated an abstract scalar system which was then imposed on actual music.)
My reason for mentioning this is because it's pretty clear that there were plenty of chants that didn't fit this scale. We have evidence in very old sources of "mismatches" and attempts to try to accommodate chants that had notes outside the scale. But since the early notation was limited to that scale, we can only guess at how many other notes may have just been dropped in early sources because of the limitations of the scale.
You may wonder at this point why they couldn't just use accidentals, but there was no such thing at the time. The B-flat again was not actually an accidental, but a completely different pitch conceptually in the original gamut.
Yet even some of the earliest sources recognize this problem with chant melodies and hint at solutions. The two Enchiriadis treatises (written ca. 900) describe something call absonia or dissonantia that allows for the lowering or raising of a note from its normal pitch. There is some discussion suggesting that this was something that needed to be employed to fix irregularities created by inadequate or faulty notation.
Notably, the Scholica enchiriadis treatise proposes an alternate notation system (called Daseian notation) that predates our modern staff notation. However, rather than octave equivalence, it is built on the principle of a kind of "perfect fifth equivalence." That is, the same pattern of tones and semitones repeats every perfect fifth, rather than every octave. It is here that we encounter the first F-sharp arguably in the medieval Western tradition (even though the note was not yet known by the name F). The Daseian scale effectively begins on the lowest note of the gamut (the equivalent of the bass G on the bottom of our modern bass staff) and creates a scale with these notes (using modern pitch names):
G-A-B♭-c-d-e-f-g-a-b♮-c'-d'-e'-f♯'-g'-a'
The pattern here is composed of whole tones and semitones, with a tone-semitone-tone-tone pattern repeating every perfect fifth.
Daseian notation never caught on in practical musical sources, however, but the few notated examples in treatises are suggestive that this scale could potentially accommodate some melodic patterns in chant that perhaps the later gamut (with only that one B/B♭ option) could not.
Nonetheless, it's clear that plainchant required musica ficta at times. (Again, the nomenclature is anachronistic, as the term musica ficta didn't emerge until a couple centuries later.) Suffice it to say that adjustments were needed. As Margarent Bent notes when discussing the history of musica ficta, this was generally to avoid melodic tritones:
The anonymous author of the 10th-century Dialogus de musica (Huglo,
1969, 1971) referred to the ‘vice’ of additional semitones outside the
‘prefixed rule’ (GerbertS, i, 272) and cited chants in which b♭, e♭,
c♯ and f♯ were required [...].
To summarize briefly so far: yes, plainchant sometimes required adjustments by semitones. However, it should be noted that opinions among theorists did differ about how far to go with this or whether it was strictly necessary in plainchant -- the special status of chant melodies as fixed led some theorists to advocate against correcting melodic tritones or only to correct them in some circumstances (like where a B-flat could be used, which was part of the standard gamut).
I'm going to skip over a lot of history of plainchant and the imposition of modal theory in later centuries after ca. 1000 (which was an additional alteration, after the imposition of a foreign scale, that restricted the possible "correct" scales for chant, and also restricted potential placement of semitones). Suffice it to say that further evidence we have of "adjustments" to pre-existing oral chants with more potential accidentals comes from chants that are notated in multiple places within the scale, i.e., with different final notes. I've seen examples of chants in early sources that appear with finals on C, F, and G in different sources, all without accidentals. Is that because of scribal confusion? (Likely in some cases.) Or is it because there were different needs of semitones at different parts of the scale or in different parts of the melody, and none of these scales based on these finals was the "best" fit, because perhaps there were more chromatic options beyond what was available in the notation at the time? In many cases, we'll never know. Yet there have been ongoing debates among chant scholars about how many types of potential inflections (even microtonal ones) may have been lost after the imposition of the standard gamut and then the modal system.
Moving on beyond plainchant, polyphonic music introduces new issues: specifically vertical/harmonic tritones and the other potential use of F♯ as leading tone, not just as tritone correction. Leading tones were not generally an issue in plainchant. Other than a few suggestive situations where we have chants notated on, for example, both finals F and G in different sources (which could indicate a flexible "leading tone" with final F and the semitone motion E-F, but not one in other cases, as would be notated with F-G), there's little indication of raising leading tones as a standard practice in monophonic chant. Once parallel organum at the perfect fifth or perfect fourth occurs, there are mentions of corrections required to (for example) make an F♯ rather than F to correctly harmonize with a B in the original chant and make a perfect interval.
In fact, once polyphony becomes a topic of extended theoretical discussion in the late 12th and 13th centuries, it's clearly assumed by theorists that singers must "correct" vertical tritones, which sometimes might involve using a F♯ to harmonize with a B. This is the origin of the term musica falsa, which later became musica ficta.
As for leading tones and ficta, there were hints at that at many treatises around that time about the need to change certain notes when approaching perfect consonances. Eventually this became standardized somewhat after the 13th-century treatise Tractatus de discantu (commonly referenced as by Anonymous II) discussed a new classification of ficta into two categories.
- Causa necessitatis, i.e., notes altered for the sake of necessity, which most typically was tritone correction, either in vertical harmonies or in melodic leaps.
- Causa pulchritudinis, i.e., notes altered for the sake of beauty, which encompassed alterations made at cadences and such where a leading tone might be raised (or sometimes the note above the local destination pitch might be lowered, particularly in melodic contexts involving a B-A motion that could be changed to B♭-A).
So to answer the original question, we know that F♯ might be introduced as ficta for a leading tone motion by the 13th century, as we have explicit discussions of such alterations. These are clearly standard by the 14th century. However, we don't really know how far back in the past such traditions may go, perhaps into the 12th century or even earlier.
But in the case of correcting tritones in polyphony, as discussed in the question, the alterations begin to occur at a much earlier date. Even by the 10th century, there appear to be references to F♯ to allow parallel perfect organum at the fifth, and there's no reason to suggest such adjustments wouldn't have been made regularly once more free polyphony evolved. Theorists would generally advise against this when possible and to employ notes already in the gamut. That is, try to use a B♭ to harmonize with an F, rather than raising the F to F♯ to harmonize with B. Or perhaps transpose the whole thing to a different mode to avoid the issue. But when B♮ is actually required (as in existing chant melody), any F present in harmonization would causa necessitatis be "corrected" to F♯. That practice would have been standard centuries even before the term musica ficta existed. There's no indication that the tritone would have ever been acceptable in such harmonizations in early polyphony, though of course perhaps some less knowledgeable singers (or ones who deviated from the theoretical rules) sang them at times in actual practice.
EDIT: I forgot to answer the second question, regarding the F-B-E harmony. The fact is that for such an early three-voice work, we really have no idea how this kind of simultaneity would have been handled. And there's no way to "correct" this to a consonance. Yes, you can get rid of the tritone(s) by rewriting it as F-B♭-E♭, but that still contains a discordant seventh. In that case, the B-E notes are also passing against a longer note F note. Thus, it's possible to perhaps view them as dissonant "passing tones" (to use a modern concept), and basically the E must be viewed as a passing dissonance, whether one sings it as E or as E♭. We know later treatises (as I discussed) would eventually privilege semitone motion into a perfect consonance, so that would prefer E over E♭ in this context. But that still leaves us with a tritone of the B then against the F. We could correct that to B♭, but that then creates a tritone against the E. Again, we correct once more, but we haven't actually created a consonance then (which is typically the goal of tritone correction). Furthermore, we seem to have examples of "passing notes" in even fairly early polyphony that allowed ascending tritones when they resolved to a perfect fifth.
My guess is Taruskin punted this issue in his edition and didn't impose ficta there because it's an ambiguous case and one could legitimately argue for different possible ficta or none, depending on which rules/principles one tries to adhere to.
EDIT2: In response to a comment asking about sources about tritone correction in early organum, let me add some information. The Enchiriadis treatises (again ca. 900) are the first and primary source showing early concern about treatment of tritones in organum. For a detailed discussion of this (as the archaic nomenclature of the Enchiriadis treatises can be a bit hard to understand at first), I'd recommend looking at Sarah Fuller's article, "Theoretical Foundations of Early Organum Theory."
The entire Daseian notational system with perfect fifth "equivalence" I discussed above seems designed to facilitate singing organum at the fifth with "adjustments" to the scale to always maintain perfect fifths (no tritones). When singing organum at the fourth, the special set of notes introduced by the notational system doesn't solve everything, so more complex rules are described. From Musica enchiriadis:
But because with the interval of a fourth sounds do not concord
sweetly at a distance of four notes throughout the whole series [of
pitches], so the symphonic song cannot be [re]produced literally as in
the others. Therefore, in this genre of singing, by a law proper to
it, pitches are adjusted to other pitches in a divine way.
(Scholica enchiriadis has a similar discussion of organum at the fourth and how it must be "diverted" to deal with the tritone.)
Now, the musical examples actually provided in the treatise don't show correction by semitone inflection -- though there are suggestive passages that seem to introduce F-sharp (and E-flat) mutations for plainchant. But again, the authors of the treatises actually generated their entire notational system and scale to fix parallel fifth organum while avoiding tritones by effectively creating "accidentals" of a sort. Their nomenclature does suggest the ability to modify pitches when necessary for tritone corrections elsewhere, though this is not discussed in detail.
For the perfect fourth situation, they instead describe a "law" of how to deviate away from parallel fourths when necessary to avoid tritones (usually allowing thirds instead for a while against a given chant melody). Thus, the Enchiriadis treatises provide the first rules for avoiding tritones in organum, though they don't describe in depth how one might perhaps use semitone inflections to avoid them (even though they built those semitone inflections into their unusual scale for organum at the fifth).
It's very clear in a number of these early treatises (pre-13th century) that tritones had to be avoided in organum. It's frankly been quite a few years since I've read many of these in depth, so I can't off the top of my head locate instances of explicit adjustments to introduce things like F-sharps. However, the Grove article I cited above by Margaret Bent on musica ficta mentions the practice in treatises of this era:
The development of a system of modal transpositions [in the 10th-12th centuries] coincided with the
rise of a clearer pitch notation which, however, had very little
capacity as yet to cope with the additional notes required for the
necessary perfection of simultaneous intervals in polyphony: f♯ and c♯
appear besides B♭ and B♮ to permit perfect intervals in parallel
organum at the 5th. Notes outside the system are recognized, usually
as undesirable distortions in chant, and hence false, but useful for
modal transposition.
Unfortunately, Bent doesn't provide any citation of specific examples or treatises at that point of the article. But if you're looking for early examples of accidentals, I suppose that's where to start.
