Für die rechtliche Prüfung gibt es eine ganz einfach Faustformel: Wenn der Komponist/Bearbeiter eines Werke schon vor länger als 70 Jahren verstorben ist, gehört das Werk zur sogenannten "Freien Musik". In dem Falle kann man selbst das Werk nachsetzen oder weiter bearbeiten, ohne lizenzrechtlich in Gefahr zu geraten. In allen anderen Fällen bedarf es des Einverständnisses des Komponisten/Bearbeiters oder deren Rechteinhaber.

In der Regel kann man die Rechteinhaber entweder über die Gema (online.gema.de/werke/) oder über die VG-Musik (vg-musikedition.de/) erfragen.

Ich habe mich in mehreren Fällen an die laut GEMA zuständigen Rechteinhaber gewandt,meistens kommt nicht viel dabei raus.
In einem konkreten Fall (Mc.Broom/The Rose) dauerte die Odyssee über ca. 2 Jahre und blieb dann doch ergebnislos. Man merkt vielmehr,daß die Leute desinteressiert sind,Genehmigungen zu erteilen,sogar dann,wenn sie an den Noten mitverdienen könnten.
Die Leute fühlen sich meist "nicht zuständig" oder sind einfach zu faul oder zu blöd,man wird oft an andere Verlage und Institutionen verwiesen,die sich dann ihrerseits nicht zuständig fühlen oder einfach überhaupt nicht antworten.

In nur einem einzigen Fall (Strube Verlag) bekam ich eine konstruktive Antwort innerhalb einer akzeptablen Zeit (9 Tage),deshalb ein verdientes Lob an Hrn. Klaus Leitner vom Strube Verlag !

Aber in den meisten Fällen lautet mein Tip an alle Kollegen:
Spart euch die Mühe,verschwendet nicht eure Zeit,wartet lieber,bis die Komponisten lange genug tot sind (was sind schon 70 Jahre? *g*),ist weniger mühsam und geht meist schneller als der Behörden-Spießrutenlauf zur Genehmigung.