Some background information (a little more objective than the stuff I've seen on some websites!) mostly from John Prebble's The Lion in the North:

In 1332, Edward Balliol, son of John Balliol, King of Scotland prior to Robert Bruce, made a bid for power, supported by "The Disinherited", (Scots barons exiled by Bruce) and a confederation of ambitious English barons.  Many of Bruce's former supporters backed Balliol (Bruce himself had always shown an eye for the main chance), and he was crowned at Scone.  He was then promptly ambushed at Annan by (I think) Thomas Randolph and Archibald Douglas, and expelled from Scotland; Douglas was elected Regent, but didn't last long.  Edward III of England came out in support of Balliol, and took Berwick Castle on the grounds that Randolph, who openly encouraged border reiving, was in breach of the Treaty of Northampton.  The Scottish forces engaged his at Halidon Hill near Berwick; the Scots were tactically outmatched, and suffered a massive defeat.  Douglas died soon after, a prisoner.  The restored Scottish king gave the southern Scottish counties to England.  Prebble continues:

"For twelve years that kingdom was in a state of anarchic civil war as successive regents challenged Balliol's rule, riding boldly across the land between his isolated castles.  John Randolph, the last male of his name and third Earl of Moray since his brother's death at Dupplin Moor, almost liberated the country with Bruce's grandson, Robert the Steward.  But the English took him on the Border and told his fiery sister Black Agnes, Countess of Dunbar, that they would kill him if she did not surrender her castle.  Let them, she said, for then she would inherit the earldom of Moray.  For six months she successfully held the castle against the Earl of Salisbury, standing boldly on its battlements with her women, watching the battering-ram below and dusting her fine gown with a linen napkin.  It was all the stuff of balladry, wherein Lord Salisbury cried "Came I early, came I late, I found Agnes at the gate"."

It seems, though, that the snatch Kat quoted is all that there is.  The stuff, then, perhaps, of nursery-rhymes rather than ballads, which is a pity.

Malcolm