Nur vorab: Staatliches Gewaltmonopol ist eine Erfindung der Neuzeit. Im Mittelalter gab es so etwas nicht.
Ich dachte dabei nicht ausschließlich an Könige (aber auch diese hatten doch die römische Univeralkirche als Schlichterinstanz, der sie sich fügen müssten (falls die Kirche es darauf anlegen würden, das zu versuchen, dann wahrscheinlich eh nur, wenn beide es freiwillig wollen), oder?), sondern auch und vor allem an einzelne Fürsten.
Okay, weil du vom Völkerrecht gesprochen hast, dachte ich, du meinst die "zwischenstaatliche" Bühne. Was die Kirche angeht: Bis in die Zeit der Kirchenreform (ab der zweiten Hälfte des elften Jahrhunderts) hatten sie bzw. der Papst als Instanz wenig bis nichts zu sagen. Im Spätmittelalter sah das dann aber tatsächlich etwas anders aus, als Konzil auf Konzil folgten (v. a. im fünfzehnten Jahrhundert, man spricht hierbei auch vom "Konziliarismus") und dort auch diverse politische Belange entschieden wurden, wie zaphod bereits gesagt hat.
Nun ja, innerhalb des Reiches gab es schon so was wie Gerichtshöfe,die auch für Streitigkeite zwischen den einzelnen Herrschaften und Fürstentümern zuständig waren. Die Kompetenz lag zunächst bei den Reichstagen,dann beim Reichskammergericht.
Hierbei konnte sogar die Reichsacht ausgesprochen und ein Reichsheer gegen den betroffenen Staat in Marsch gesetzt werden.
Jawohl, alles richtig, nur verlässt man hierbei das Mittelalter. Was die Verfassungsgeschichte des Heiligen Römischen Reiches angeht, so lässt man sie gerne mit dem Reichstag von Worms 1495 beginnen; der Reichshofrat und das Reichskammergericht wurden erst später begründet. Die Entwicklung zu diesen Institutionen setzte freilich früher ein.
Mit den Staufern hat man gewissermaßen mit Experimenten im Zusammenhang mit übergeordneten Gerichten angefangen, die im zwölften Jahrhundert allerdings noch wenig Anerkennung gefunden haben, was man daran erkennen kann, das angeklagte Fürsten sich meist von diesen Gerichten fernhielten, was generell der früh- und hochmittelalterlichen Mentalität entsprach, nicht auf Hoftagen zu erscheinen, wenn man mit den zu erwartenden Beschlüssen nicht einverstanden war. Ein berühmtes Beispiel ist die Abwesenheit Heinrichs des Löwen auf zwei (soweit ich mich erinnere) Gerichtsterminen 1179 und 1180.
Aber erst die lange Abwesenheit eines Königs im Reich unter Wenzel, Sigismund und Friedrich III. machte eine "zentralere" Instanz notwendig, um Streitigkeiten zwischen den Fürsten - die im Mittelalter sonst immer an den Hoftagen durch königliche Vermittlung entschieden wurden - zu beheben, was dann schließlich in die Gründung von Reichskammergericht und Reichshofrat mündete (1500 bzw. 1512, wenn ich mich jetzt nicht ganz irre).
Apropos Vermittlung: Bestand zwischen zwei Fürsten im Früh- und Hochmittelalter ein Konflikt, so schaltete man sofort Vermittler ("mediatores") ein, die im Idealfall einen guten Draht zu beiden Parteien hatten einen Kompromiss zwischen diesen aushandelten; lehnte eine Partei ab, so schlossen sich die mediatores der anderen an. Die Rolle des Vermittlers übernahm hierbei häufig der König, aber auch kleinere Fürsten. Um den Konfliktpartner zum Einlenken bzw. zum Kompromiss zu zwingen, ging man häufig zur Fehde und zu Zerstörungen von Burgen und Ländereien über (inwieweit Menschenleben hierbei Opfer wurden weiß ich nicht; Forscher streiten sich in der Hinsicht) - ohne aber dass die Verhandlungen gänzlich abgebrochen worden wären! Und schließlich ging das mit den Vermittlern und der Fehde solange weiter, bis ein Kompromiss gefunden wurde. Und wie gesagt: Durch das Fehlen des Königs als Vermittler im Spätmittelalter griff man immer mehr und mehr auf das Gericht als Entscheidungsinstanz zurück. Stellvertretend für das Mittelalter ist das allerdings nicht.
Meine ganzen Ausführungen beziehen sich übrigens ausschließlich auf das Ostfränkische bzw. Heilige Römische Reich. Wie es in den anderen Staaten aussah, weiß ich nicht, aber zumindest in Frankreich und England haben sich staatliche Institutionen bereits früher entwickelt, so (denk ich mal...) auch das Gerichtswesen.
Als Literaturipps hinterlasse ich so ziemlich alle aufsätze von Gerd Althoff, v. a. die, die in seinem Sammelband "Spielregeln der Politik im Mittelalter" erschienen sind.