Citation: 4A_564/2021 E. A

A.a. A.________ (Spieler, Beschwerdeführer 1) ist ein Fussballspieler aus U.________. B.________ (Beschwerdeführerin 2) ist die Fussballergewerkschaft von U.________, die seit 2011 Mitglied der internationalen Spielergewerkschaft FIFPRO ist. Die Fédération Internationale de Football Association (FIFA, Beschwerdegegnerin) ist ein Verein schweizerischen Rechts mit Sitz in Zürich. A.b. Am 9. Dezember 2016 beschloss der Dringlichkeitsausschuss (Emergency Board) des nationalen Fussballverbands von U.________ (nFA) eine Änderung der Zusammensetzung ihrer Kammer zur Beilegung von Streitigkeiten (nFA National Dispute Resolution Chamber, nFA NDRC). Der Dringlichkeitsausschuss entliess die bestehenden Schiedsrichter, einschliesslich des Vorsitzenden, und setzte neue, vom nationalen Fussballverband ausgewählte Schiedsrichter ein. Der Dringlichkeitsausschuss führte zudem einige Änderungen der anwendbaren Verfahrensordnung des nFA NDRC (nFA NDRC Procedural Rules) ein. Nachdem die FIFPRO über ihr Mitglied, die Fussballergewerkschaft B.________, von diesen Änderungen erfahren hatte, liess sie dem nationalen Fussballverband am 14. Dezember 2016 ein Schreiben zukommen, in dem sie ihre Unzufriedenheit mit den erfolgten Änderungen zum Ausdruck brachte, die ohne vorherige Anhörung der Fussballergewerkschaft B.________ vorgenommen worden seien. Die FIFPRO forderte den nationalen Fussballverband auf, die Situation zu bereinigen. Am 4. Januar 2017 richtete der nationale Fussballverband ein Antwortschreiben an die FIFPRO, in dem er unter anderem ausführte, dass die Änderungen vorgenommen worden seien, um bestimmte Verfahrensregeln zu verbessern, Verfahrensabläufe zu beschleunigen, die Anzahl der Schiedsrichter zu erhöhen und die Unabhängigkeit, Sachkenntnis und Unparteilichkeit der Schiedsrichter zu gewährleisten und zu erhalten. Als Reaktion auf die Beschlüsse der nFA vom 9. Dezember 2016 fand am 7. Februar 2017 in den Büroräumlichkeiten der nFA eine Sitzung statt, an der die Union des Associations Européennes de Football (UEFA), die European Club Association (ECA), die European Leagues, die FIFPRO sowie die nFA samt nationaler Interessengruppen (so unter anderem die Fussballergewerkschaft B.________) teilnahmen. Das Protokoll dieser Sitzung fasst die Ereignisse zusammen, die zu den Beschlüssen vom 9. Dezember 2016 geführt haben und legt die nächsten Schritte und Zeitabläufe fest, um die Situation zu bereinigen und verschiedene andere Ziele zu erreichen. In Bezug auf das nFA NDRC erklärten die Parteien des Treffens, dass der nationale Fussballverband zugestimmt habe, den Spielern/Vereinen die sechs freien Plätze auf der Liste der Schiedsrichter des nFA NDRC zuzuweisen. Ausserdem sollen Diskussionen geführt werden, um die Anzahl der Schiedsrichter auf 15 zu erhöhen. Die FIFPRO war mit diesem Vorgehen vorerst einverstanden, wies jedoch darauf hin, dass eine solche Struktur nicht ganz den einschlägigen Anforderungen entspreche. A.c. Kurz darauf bezeichnete die Spielergewerkschaft B.________ gestützt auf eine der Vereinbarungen, die anlässlich der Sitzung vom 7. Februar 2017 geschlossen wurden, drei Personen für die neue Liste der Schiedsrichter des nFA NDRC, darunter auch C.________. Am 15. August 2018 entschied C.________ als Einzelschiedsrichter des nFA NDRC eine arbeitsrechtliche Streitigkeit zwischen A.________ und dem Fussballclub D.________ von U.________. C.________ erachtete die Kündigung des Arbeitsvertrags durch den Spieler als zulässig. Der Entscheid enthielt eine ausführliche Begründung und sah vor, dass er nach Art. 36 der nFA Verfahrensordnung endgültig sei. Die Verfahrensordnung sah die Möglichkeit einer Anfechtung des Entscheids nicht vor. Am 3. September 2018 ordnete der Präsident des nFA NDRC an, den Fall des Spielers gegen seinen ehemaligen Club zu überprüfen, dies deshalb, weil der Präsident des nFA NDRC der Meinung war, dass die Entscheidung in Verletzung zwingender Bestimmungen von U.________ sowie des nationalen Fussballverbands ergangen sei. Weder der Spieler noch der Club hatten einen Antrag auf Wiedererwägung des Entscheids gestellt. Am 4. September 2018 entschied das nFA NDRC in der Zusammensetzung von E.________, F.________ und G.________, dass der Entscheid vom 15. August 2018 gegen zwingende Vorschriften von U.________ verstosse und daher nichtig sei. Zudem setzte das nFA NDRC eine neue Hauptverhandlung im Verfahren an. Am 14. September 2018 erliess das nFA NDRC in gleicher Besetzung ein neues Urteil in der Sache und entschied, A.________ habe den Arbeitsvertrag mit dem Fussballclub D.________ nicht wirksam aufgelöst. In der Zwischenzeit hatte der Spieler bereits einen Arbeitsvertrag mit einem neuen Club unterzeichnet. Im Ergebnis wurde der Spieler zurück in sein Arbeitsverhältnis mit D.________ beordert, da seine Registrierung beim neuen Club vom Registrierungsausschuss des nationalen Fussballverbands nicht genehmigt wurde. Der Spieler weigerte sich, zu D.________ zurückzukehren und wurde arbeitslos. A.d. Mit Schreiben vom 10. Oktober 2018 wandte sich die FIFPRO an den nationalen Fussballverband und drückte ihre entschiedene Missbilligung der Art und Weise aus, wie dieser den Streitfall A.________/D.________ behandelt habe. Zudem forderte die FIFPRO den Verband auf zu erläutern, auf welcher Rechtsgrundlage die neu ernannte Dreierbesetzung befugt war, die von C.________ getroffene Entscheidung zu überprüfen und aufzuheben. Am 23. Oktober 2018 antwortete die nFA der FIFPRO, dass C.________ die Gesetzgebung missachtet, gegen zwingende Bestimmungen von U.________ verstossen und die Integrität des Schiedsgerichts in Frage gestellt habe. Die nFA erläuterte zudem den Inhalt des Rechtsstreits und wies darauf hin, dass das Schiedsgericht ein aus drei Schiedsrichtern bestehendes Panel ernannt habe, um die Schwere des Verstosses zu überprüfen. Am 2. November 2018 beschloss der Dringlichkeitsausschuss des nationalen Fussballverbands gestützt auf Art. 48 der Statuten der nFA in Verbindung mit Art. 4 Abs. 5 der Verfahrensordnung des nFA NDRC, C.________ als Schiedsrichter zu entlassen. Mit Schreiben vom 13. November 2018 drückte die FIFPRO ihre Missbilligung über das beschriebene Vorgehen aus und forderte die nFA auf, C.________ wieder als Schiedsrichter des nFA NDRC einzusetzen. Das Schreiben blieb folgenlos. Am 11. Dezember 2018 ernannte der Dringlichkeitsausschuss der nFA gestützt auf Art. 48 Abs. 2 der Statuten der nFA in Verbindung mit Art. 2 Abs. 2 der Verfahrensordnung des nFA NDRC einen neuen Schiedsrichter an Stelle von C.________. A.e. Mit Schreiben vom 29. März und 9. Dezember 2019 beschwerten sich die FIFPRO und die Beschwerdeführer bei der Disziplinarkommission (Disciplinary Committee) der FIFA und beantragten die Eröffnung eines Disziplinarverfahrens gegen den nationalen Fussballverband und dessen Funktionäre. Am 7. Februar 2020 bestätigte die FIFA den Eingang der Beschwerden. Sie richtete ihr Antwortschreiben einzig an die FIFPRO und teilte dieser unter anderem mit, dass die FIFPRO zwar berechtigt sei, eine Anzeige über ein Verhalten einzureichen, das mit dem FIFA Disziplinarreglement (Disciplinary Code) und/oder anderen Bestimmungen der FIFA als unvereinbar angesehen werde; daraus folge aber nicht, dass die FIFPRO gemäss Art. 27 des FIFA Disziplinarreglements Partei des Verfahrens werde. Die FIFA sei unter anderem wegen der fehlenden Aktivlegitimation der FIFPRO nicht verpflichtet, ein Disziplinarverfahren zu eröffnen. Aus diesem Grund werde die FIFA der FIFPRO auch keine Informationen zum Stand eines möglichen Verfahrens vor der Disziplinarkommission der FIFA erteilen. A.f. Am 21. Februar 2020 beanstandeten die FIFPRO und die Beschwerdeführer gegenüber der FIFA das erhaltene Schreiben vom 7. Februar 2020. Sie forderten die FIFA auf, auf der Grundlage der erhobenen Beschwerden ein Disziplinarverfahren gegen den nationalen Fussballverband einzuleiten; zudem seien die FIFPRO und die Beschwerdeführer über alle Entwicklungen im Zusammenhang mit diesem Verfahren zu informieren. Gleichzeitig erklärten die FIFPRO und die Beschwerdeführer, dass sie, falls die FIFA sie nicht bis zum 20. März 2020 über Entwicklungen in Bezug auf die Beschwerden informiere, keine andere Wahl hätten, als von einem Entscheid der FIFA auszugehen, kein Disziplinarverfahren gegen den nationalen Fussballverband einzuleiten. Eine Antwort der FIFA auf das Schreiben vom 21. Februar 2020 blieb aus. Am 24. März 2020 setzten die FIFPRO und die Beschwerdeführer der FIFA eine letzte Frist bis zum 27. März 2020 an, um den gestellten Anträgen nachzukommen, ansonsten von einer Verweigerung der Verfahrenseinleitung bzw. einer Rechtsverweigerung ausgegangen werde, was vor dem Tribunal Arbitral du Sport (TAS) angefochten werden könne. A.g. Am 26. März 2020 eröffnete die Disziplinarkommission der FIFA aufgrund der gestützt auf die erhobenen Anzeigen durchgeführten Untersuchung ein Verfahren gegen die nFA. Die Beschwerdeführer wurden darüber nicht informiert, da sie nicht als Parteien angesehen wurden. Am 4. Mai 2020 erliess die Disziplinarkommission der FIFA einen Beschluss, welcher der nFA am 15. Mai 2020 zugestellt wurde. Darin wurde das gegen die nFA eingeleitete Disziplinarverfahren für abgeschlossen erklärt.