Eighteenth Century Collections Online is a database that includes no less than 180,000 British and American publication, including garlands and some broadsides. Its coverage of music books is good, but probably not complete.

A search finds not a single instance of the phrases, "My name is William/ Robert/ Captain Kidd," "As I sail/ed, as I sail/ed," or "What wond'rous/ wondrous/ wonderous love is this, O."

The earliest appearance in ECCO of "Ye Jacobites by Name" is in the anonymously edited "Scotish [sic] Songs. In Two Volumes" (London: J. Johnson & J. Egerton, 1794), II, p. 257. Some of the collection's songs are attributed to Burns. This is unattributed.

The second half of the tune is a little (but noticeably) different from that popularized (I believe) by Ewan MacColl.

ECCO contains no exx. of the very similar "Aikendrum," words or music.

The British Library Catalog indexes nothing of great age under the title "Captain Kidd"

Nor does the Bodleian Ballads site contain anything under "Captain Kidd" or "Kidd."

Washington Irving quotes a half-dozen lines from the ballad in his sketch "Kidd the Pirate" (1824).

Any other search suggestions?