> in that case, you would expect a paper trail.
Possibly not. If the piece was composed by a regimental piper or pipe-major, it may well have circulated aurally or in manuscript for years without publication.
It's an easy tune to memorize. I did so in no time when I was about eleven, after hearing it two or three times in a commercial for Campbell's "tender-hearted beans."
The tune was undoubtedly better known to the general public than the title. (This is true of many pieces today.) Hence "The Irishman's Toast," "Scotland for Ever," "Brave Scotland," "Bonnie Lassie," and, perhaps, the confusion with "O'Donnell Abu." If the Victorian journalists did not know the title of one of the tunes played, they could simply ask.
What we know for certain is that a tune called "Scotland for Ever" (the title given to "Scotland the Brave" by Macdonald in 1893) was played in 1869) and "Scotland the Brave" from at least 1883.
If no other tune is known to have gone by these titles, the simplest interpretation is that today's "Scotland the Brave" was played - in easily recognizable form - by Highland regiments as early the latter 1860s, but was not published (and then anonymously) till the 1890s. By 1897, even some uillean pipers like Corrigan were playing it.