I posted Bruce's question on the Scots Music mailing list, and the only reply I got was from Kate Dunlay, who is associated with the group Puirt A Baroque.

Quote follows:

Well, I'm not totally convinced about all of the following, but David Johnson wrote that some anonmymous composer simplified the two-strain melody "Of A' the Airts the Wind Can Blaw" (which is Robert Burns' song to William Marshall's "Miss Admiral Gordon's Strathspey") in the mid-19th century and came up with the song, "The Bonny Bonny Banks of Loch Lomond." He also gives an earlier song, "The Lowlands of Holland" which has only the first strain of the tune. But George Emmerson says it is a set of the old air "Kind Robin." As to when it first appears as "Loch Lomond" I am no help. It is not in Nathaniel Cooke (1854) or Pittman, Brown, MacKay (1877) either.