Just a few thoughts on this interesting topic:

There's a bit of confusion in the above discussions about whether people are referring to the lyrics, the melody, or both. The words of many ballads can be traced back far further than any of the melodies that may have been used for them, and it will generally be easier to find written words than written notation.

If you go for a church hymn like "O Come O come Emmanuel", you're not looking at a purely folk process - even if the melody goes back a long way, songs like this would have been transmitted and written down in a form accepted by the church and kept that way.

One problem with medieval words is that they are barely intelligible to the modern ear, and you'd have to translate/update them, and/or find other versions that have been updated over the years.

I think the idea of tracing a "song family" of related songs is a good one and would enable you to follow whatever paths your research revealed as being traceable. Starting now and working backwards might be more feasible than finding an old song and working forwards, although that's just my hunch.

Hope you come back to tell us what you find!

Marje