Brian,
Yes, Riddles is one of the few examples, 15th century I think.

Can't remember ever seeing references to Lord Thomas earlier than the broadsides. I don't think it's in Percy's Folio Ms. Foreign analogues may be earlier, but then the tricky question of who translated it comes in.

Again there are plenty of references to Chevy Chase prior to print.

Sir Andrew Barton is in the Folio Ms but these can't predate print. There was an early ms version in York Minster Library but it was nicked some time c1900. Luckily it was printed in the Surtees Society volumes before it went astray. The event itself happened (1511) shortly after print was starting to get under way in England.

Tamlene. Just as likely this refers to the early version of Brian O'Lynn which in Scotland was called Tam O'Lin. Undoubtedly a few of the ballads predate print but not a lot!

Regarding the Scottish versions, it's difficult to know to what extent the interference of antiquarian poets created/re-created these. It's common knowledge that Scott was following Percy's precedent and most of the others were part of Scott's circle at one time or another, and as you know there is at least one amongst them whose published material is ludicrous (IMHO he hastily added).