I'm interested in this 'oral formulaic' idea. Does it mean people had 'templates' in their heads, or is it something more like 'floating verses' of blues and folk music?

The other thing with translation however achieved would be the need for the new words to fit to the metre of the tune or be fitted to a new tune or a bit of both depending on cross-cultural tastes in tunes.

A snippet that fascinated me from the Bragg programmes was that somebody said that it was mostly rich medieval women who paid minstrels. I gather that 'minstrels' is itself another minefield.

On the classes/social strata question, I can see lots of ways that songs might go across these barriers, though in some cases they would need translation eg for a long time the upper strata in England spoke French then French and English. See David Crystal's Encyclopedia of the English Language on this. Also, given differing dialects of what came to be English as a national language, a fair amount of change if songs moved through lower classes across England. Within my lifetime I have occasionally had difficulties understanding broad dialect/accent eg once in Birmingham. If somebody from 12th century England was here, I doubt we would understand much of what they said.
I'm thinking even with Shakespeare it would take a while to get attuned. Vowel shifts, grammar and lexical changes, etc.