The Church never had a problem with the tritone, despite the urban legend. It had limited use in church music because it was hard to sing, and that was it.

Dick's YouTube example is pretty unadventurous - I invent alto lines like what Sue Miles was doing all the time without dignifying them with the name "counterpoint". There is much more ingenious stuff from outside the British Isles - the "tenores" or Sardinia, the choral traditions of Georgia. These are almost certainly much older than Western art music counterpoint and have developed rather independently with their own rules.

One odd practice that you don't get in post-mediaeval music, but do get in Georgian folk and in the early Western Middle Ages: three-part textures where the middle part harmonizes with both outer parts, but the outer parts don't harmonize with each other - there isn't necessarily any way to analyze the music as a sequence of "chords". You might get two stacked fourths, and an unresolved minor seventh between the outer voices. This sort of thing is why it is sometimes thought that Western counterpoint derives from Caucasian folk tradition - the West lost that sort of effect, Georgia kept it.