PhilE –   I totally agree with you that your "Old Religion" is "a weird magical belief system". If Christianity started as a Jewish sect it has travelled a long way since and, leaving aside Orthodox Christianity of which I know nothing, it seems to have done much of that travelling in Western Europe, not least in Britain itself (look at the number of missionaries that originated from here in the "dark ages".) As such it is worth looking at what this western Christianity is built on. I'd argue that a lot of the "weird magical" practices, its iconography and relic veneration, its magical transubstantiation, its festivals and celebrations and even its version of heaven and hell owe a lot to the preceding beliefs of its followers.

"If you take out all the old idols, reconsecrate the ground and dedicate the building to Christian worship …. what you've got at the end of it is a 1000-year-old Christian church."   True it's a 1000-year-old Christian church but what has Christianity become during the 1000+ years? You remove the idols and replace them with "saints", many of whom scholars now believe were either total fabrications (St. Christopher) or real people who had grafted onto them the attributes of earlier deities (St. Bridget/Bridget of Kildare/Bride). (You also fill your churches with carvings of "green men") You also carry out your worship when and where the people would have been worshipping their pre-Christian deities. Although those people might nominally be practicing Christians, it makes you wonder how much their actual belief system, as opposed to the title under which they practiced it, had to change.

Perhaps, in addition, the two systems ran along side each other (as they seem to do today with some Catholics still happy to resort to fortune tellers, mediums etc.) As well as your example from Tam Lin, the author(s) of Thomas the Rhymer seem to have been quite prepared to accept a fairy realm existing in parallel to a Christian Heaven and Hell.

"Don't you see yon narrow, narrow road,
So thick beset with thorns and briars?
That is the road to righteousness,
Though after it but few enquire."
"Don't you see yon broad, broad road,
Lying lies across the lily leaven?
That is the road to wickedness,
Though some call it the road to heaven."
"Don't you see yon bonnie, bonnie road,
Lying across the ferny brae?
That is the road to fair Elfland,
Where you and I this night must go."

Wimberly notes that most "magic" in the Child ballads seems to act totally independently of Christian belief; for example in "Willie's Lady" the disenchantment involves a type of counter-spell rather than any recourse to priests, church or God. Even Tam Lin was not rescued by Christian "magic" or because he was Christian but by a type of counter-spell. Wimberly gives plenty of other examples in his chapters on enchantment and disenchantment which have little to do with Christian teaching or accepted Christian practice so we have both the adoption of "pagan" practices by the church (saints etc) and the parallel thread of non-Christian magic, both of which existed in the population and probably influenced its song writing.

I don't think for a moment that the songs we sing today, no matter how old, were created by anything other than "practicing Christians" of some sort or another and therefore include plenty of the belief system that Christianity evolved into but I think that that belief system contains fragments of its predecessors and that those Christians also carried on a number of their pre-Christian "religious" cultural beliefs and practices in parallel with their church attendance. I don't think we'll ever know for sure which bits are which any more than we'll know for sure who wrote some of the songs, when, where or why – I'm just glad they were written.