Answer: That is a really interesting one. Actually the modes and harmony are kind of at odds with each other. There is a very good book that touches on this, Between Modes and Keys, by Joel Lester (Pendragon, 1989). The modes were part of a monophonic tradition, and polyphony has a tendency to reduce the modes essentially to two, the modern major and minor.

For example, the interplay of voices leads to the desire for leading tones in dominant harmony, so that a performer or composer is tempted to sharp the 7th in Dorian or Mixolydian or Phrygian. So Mixolydian then becomes indistinguishable from Ionian (major), and Dorian turns into melodic minor. In Lydian mode there was a frequent practice of flatting the 4th degree, which converts Lydian into major. Into the eighteenth century it was still common to write the key signature for, say, G minor with one less flat, as if it were Dorian, yet the other flat was written in as an accidental or was expected to be supplied by the player, converting the key to minor. And so on. This is how we ended up with two basic modes; it was the evolution of harmonic thinking applied to modal melody.

But what you want to have is practical advice on creating what could be called modal harmony. We're modern people and will hardly be able to avoid thinking in terms of chords, so the first principle will be that the chords you use need to stick to the notes of the mode, with only occasional departures. You ask whether the modal melody needs to include all the notes of the mode: what it needs, as you suggest, is to include at least the notes that characterize the mode. For example, in a D Dorian piece you want to make sure to use that B natural (the major sixth above the tonic is what sets Dorian apart from normal minor). Examples in popular style could be taken from old fiddle and folk tunes, many of which are in Dorian or Mixolydian or Aeolian (natural minor). Here's the first part of Red Haired Boy, which is Mixolydian. What makes Mixolydian different from major is the low seventh degree (looks like G major, but without the F sharp):

In answer to the second part of your question, no, you don't need to include chords whose roots are the characteristic tones of the mode. The characteristic tone might happen to be the 3rd or 5th in a chord. For Red Haired Boy the F natural fits well in a minor v chord (D minor here), though you could also use F major:

"Scarborough Fair" is in Dorian, with the characteristic major sixth replacing the minor sixth of modern minor. It can easily be harmonized with IV (G major in D Dorian as below):

It's harder to find tunes in Phrygian, but we can make one up for illustration. You're right that a characteristic of Phrygian is the low second degree: F natural in E Phrygian. No other traditional mode starts with a half step (I'm excluding the theoretical "Locrian mode"). We could harmonize that with d minor, showing that the characteristic tone doesn't have to be the root of a chord:

Of course, to our ears the above has a strong tendency to sound like it's in C major but just not ending on the right note. You could introduce a non-modal tone to strengthen the cadence to E at a phrase ending. A leading tone like the D# below would pretty much have to be harmonized with a B major or B7 chord, though, and that introduces not one but 2 non-modal tones:

The more you do that sort of thing, the less this sounds like Phrygian. But inconsistency is not necessarily bad in music.

Another approach is to start like the old polyphonists did, with a single melody and add more polyphonic voices. The other voices are adapted to the primary melody following typical principles of counterpoint (our Counterpointer software teaches that). Traditional modal harmony would not be built on a "chord progression," which is a modern concept; it would arise from the interplay of voices.

Whatever you do in modal writing, the listener may still not be hearing the tonic in the way you expect. But we say, "if it sounds good, do it."