I just found another song in Johnson's Museum, submitted by Burns, called 'O can ye labour lea, young man?'

The first line is 'I feed a lad in Roodmas' and the tune is what we now use for Auld Lang Syne. The notes say that '...this old tune was modelled into a strathspey, called the Miller's Daughter which Sheild selected for one of his airs to his overture to Rosina; and Gow afterwards printed under the name of 'Sir Alexander Don's Strathspey',

So the folk process really has worked on Auld Lang Syne!

It's strange that Burns actually knew both tunes but the fragment we know as 'Auld Lang Syne', submitted by him, was set to the much lesser known one.