Sachverhalt:
A. Die Strafjustiz von Serbien und Montenegro ermittelt gegen X._ und Mitangeschuldigte wegen Zugehörigkeit zu einer terroristischen Organisation und weiteren Straftaten. Auf Verhaftsersuchen von Interpol Belgrad hin und gestützt auf eine provisorische Haftanordnung des Bundesamtes für Justiz, Abteilung Internationale Rechtshilfe, Sektion Auslieferung (BJ), wurde X._ am 14. Januar 2004 an seinem Wohnort im Kanton Glarus verhaftet und in provisorische Auslieferungshaft versetzt. Anlässlich seiner gleichentags erfolgten Befragung widersetzte sich der Verfolgte einer vereinfachten Auslieferung an Serbien und Montenegro. Am 23. Januar 2004 ersuchte die Botschaft von Serbien und Montenegro in Bern um Auslieferung des Verfolgten. Das Ersuchen wurde mit Eingaben vom 9. Februar und 22. März 2004 ergänzt.
B. Mit Entscheid vom 7. April 2004 bewilligte das BJ die Auslieferung des Verfolgten an Serbien und Montenegro. Der Auslieferungsentscheid erging "unter dem Vorbehalt eines allfälligen bundesgerichtlichen Entscheids über die Einsprache des politischen Delikts". Gegen den Auslieferungsentscheid des BJ gelangte X._ mit Verwaltungsgerichtsbeschwerde vom 5. Mai 2004 an das Bundesgericht (Verfahren 1A.116/2004). Er beantragt im Hauptstandpunkt die Abweisung des Auslieferungsersuchens. Das BJ schliesst mit Vernehmlassung vom 14. Mai 2004 auf Abweisung der Beschwerde. Der Beschwerdeführer replizierte am 24. Mai 2004.
C. Mit separater Eingabe vom 7. April 2004 stellte das BJ beim Bundesgericht den Antrag, die Einrede des Verfolgten, wonach er politisch verfolgt werde, sei abzulehnen (Verfahren 1A.80/2004). Zur Begründung verweist das BJ auf die Erwägungen des Auslieferungsentscheides. Der Verfolgte hält mit Vernehmlassung vom 20. April 2004 an der Einrede des politischen Deliktes fest und beantragt im Hauptstandpunkt die Abweisung des Auslieferungsersuchens. Mit Replik vom 5. Mai 2004 hält auch das BJ an seinem Rechtsbegehren fest. Der Verfolgte duplizierte mit Eingabe vom 1. Juni 2004.

Das Bundesgericht zieht in Erwägung:
1. Die Beurteilung von Auslieferungsersuchen des Staatenverbundes von Serbien und Montenegro richtet sich nach dem Europäischen Auslieferungsübereinkommen vom 13. Dezember 1957 (EAUe; SR 0.353.1) sowie den beiden Zusatzprotokollen zum EAUe vom 15. Oktober 1975 bzw. 17. März 1978 (SR 0.353.11-12), denen beide Staaten beigetreten sind. Soweit dem Verfolgten die Beteiligung an einer terroristischen Gruppierung vorgeworfen wird, ist sodann das Europäische Übereinkommen zur Bekämpfung des Terrorismus vom 27. Januar 1977 (EÜBT, SR 0.353.3) zu berücksichtigen, welches von beiden Staaten ebenfalls ratifiziert wurde (vgl. <ref-ruling> E. 1 S. 357; <ref-ruling> E. 9a S. 577). Das EÜBT ist für Serbien und Montenegro seit dem 16. August 2003 in Kraft. Soweit die genannten Staatsverträge bestimmte Fragen nicht abschliessend regeln, ist das schweizerische Landesrecht anwendbar, namentlich das Bundesgesetz über internationale Rechtshilfe in Strafsachen vom 20. März 1981 (IRSG; SR 351.1) und die dazugehörende Verordnung vom 24. Februar 1982 (IRSV; SR 351.11; vgl. <ref-law>; <ref-ruling> E. 1 S. 357).
1.1 Der Verfolgte hat im Auslieferungsverfahren geltend gemacht, er werde aus politischen Gründen strafrechtlich verfolgt.
1.1.1 Über ausländische Auslieferungsersuchen entscheidet das BJ (<ref-law>). Macht der Verfolgte geltend, er werde eines politischen Deliktes bezichtigt, oder ergeben sich bei der Instruktion ernsthafte Gründe für den politischen Charakter der Tat, so entscheidet das Bundesgericht darüber auf Antrag des Bundesamtes und nach Einholung einer Stellungnahme des Verfolgten (<ref-law>; vgl. <ref-ruling> E. 1.1.1 S. 357 f.). Das Verfahren der Verwaltungsgerichtsbeschwerde (<ref-law> bzw. Art. 97 ff. OG) ist dabei sinngemäss anwendbar (<ref-law>).
1.1.2 In <ref-ruling> hat das Bundesgericht die Zuständigkeiten für Auslieferungsfälle im Rahmen der Bundesrechtspflege präzisiert. Danach entscheidet das Bundesgericht (nur) über die Einrede des politischen Deliktes als erste und einzige Instanz. Zu den übrigen Auslieferungsvoraussetzungen hat das BJ einen erstinstanzlichen Auslieferungsentscheid zu fällen. Dieser erfolgt unter dem Vorbehalt des bundesgerichtlichen Entscheides über die Einsprache des politischen Deliktes und ist mit Verwaltungsgerichtsbeschwerde beim Bundesgericht anfechtbar (<ref-ruling> E. 1.1.3-1.1.4 S. 358 f.). Auch in Fällen, bei denen Einreden des politischen Delikts erfolgen oder sich bei der Instruktion entsprechende Fragen stellen, hat das BJ die notwendigen Sachabklärungen hinsichtlich aller Auslieferungsvoraussetzungen vollumfänglich vorzunehmen (<ref-ruling> E. 1.1.2 S. 358).
1.1.3 Im vorliegenden Fall erliess das BJ am 7. April 2004 einen Auslieferungsentscheid. Dieser erfolgte "unter dem Vorbehalt eines allfälligen bundesgerichtlichen Entscheids über die Einsprache des politischen Delikts". Gegen den Auslieferungsentscheid des BJ hat der Verfolgte am 5. Mai 2004 Verwaltungsgerichtsbeschwerde erhoben (Verfahren 1A.116/2004). Mit separater Eingabe vom 7. April 2004 stellte das BJ beim Bundesgericht den Antrag, die Einrede des politischen Deliktes sei abzulehnen; zur Begründung verweist das BJ auf die Erwägungen des Auslieferungsentscheides. Der Verfolgte hält in seiner Stellungnahme an der Einrede des politischen Deliktes fest (Verfahren 1A.80/2004). Es erfolgte in beiden Verfahren ein doppelter Schriftenwechsel.
1.1.4 Da im Beschwerdeverfahren und im Verfahren betreffend Einrede des politischen Deliktes inhaltlich konnexe auslieferungsrechtliche Fragen zu behandeln sind, rechtfertigt sich eine gemeinsame Behandlung im Rahmen des vorliegenden Urteils. Die Bestimmungen über die Verwaltungsgerichtsbeschwerde sind in beiden Verfahren (sinngemäss) anwendbar (<ref-law>).
1.2 Der Auslieferungsentscheid des BJ kann mit Verwaltungsgerichtsbeschwerde beim Bundesgericht angefochten werden (Art. 55 Abs. 3 i.V.m. <ref-law>). Die Sachurteilsvoraussetzungen von Art. 97-114 OG sind erfüllt.
1.3 Zulässige Beschwerdegründe sind sowohl die Verletzung von Bundesrecht, inklusive Staatsvertragsrecht (einschliesslich Überschreitung oder Missbrauch des Ermessens), als auch die Rüge der unrichtigen oder unvollständigen Feststellung des rechtserheblichen Sachverhalts; der Vorbehalt von Art. 105 Abs. 2 OG trifft hier nicht zu (Art. 104 lit. a-b OG; vgl. <ref-ruling> E. 2b/bb S. 72). Soweit die Verwaltungsgerichtsbeschwerde gegeben (und die staatsrechtliche Beschwerde daher ausgeschlossen) ist, kann auch die Verletzung verfassungsmässiger Individualrechte (bzw. der EMRK und des UNO-Paktes II) mitgerügt werden (<ref-ruling> E. 2a S. 137; <ref-ruling> E. 2c S. 158 f.; <ref-ruling> E. 1b S. 375).
1.4 Das Bundesgericht ist an die Begehren der Parteien nicht gebunden (<ref-law>). Es prüft die Auslieferungsvoraussetzungen grundsätzlich mit freier Kognition. Im Rahmen der Verwaltungsgerichtsbeschwerde befasst es sich jedoch nur mit Tat- und Rechtsfragen, die Streitgegenstand des Verfahrens bilden (vgl. <ref-ruling> E. 1d S. 136 f.; <ref-ruling> E. 2d S. 372, je mit Hinweisen).
2. Der Verfolgte erhebt die Einrede, er werde aus politischen Gründen verfolgt. Es handle sich um einen "propagandistischen Schuldvorwurf in einem politisch motivierten Prozess". Ziel des serbischen Ersuchens sei es, die kosovo-albanischen Bürgerkriegsgegner (namentlich die Nachfolgeorganisationen der UCK) sowie die durch die UNO und die OSZE eingesetzten "multiethnischen" Polizeikräfte im Kosovo (MEP) als "Terroristen" zu diskreditieren. Auch die Auslieferungsvoraussetzung der beidseitigen Strafbarkeit sei nicht erfüllt. "Abgesehen von einem diffusen, politisch motivierten und schwammig gehaltenen Terrorismusvorwurf" werde aus dem Ersuchen sowie dessen Ergänzungen und Beilagen "nicht einmal ansatzweise klar, was dem Beschwerdeführer eigentlich zur Last gelegt wird". Zwar werde diesem vorgeworfen, er sei (in den Jahren 1999-2000 sowie 2002-2003) in Südserbien an Straftaten gegen serbische Sicherheitskräfte beteiligt gewesen und anschliessend in die Schweiz geflüchtet. Diesbezüglich habe der Verfolgte jedoch Alibis nachgewiesen. Die Lage in Südserbien sei nach wie vor bürgerkriegsähnlich und sehr angespannt. Dem Beschwerdeführer als Repräsentanten der verhassten und von der serbischen Regierung bekämpften albanischen Minderheit drohe in Serbien eine menschenrechtswidrige Behandlung. Die vom BJ verfügte Auslieferung verstosse gegen verschiedene Bestimmungen der EMRK und des UNO-Paktes II.
3. Die Auslieferung wird nicht bewilligt, wenn die strafbare Handlung, derentwegen sie begehrt wird, vom ersuchten Staat als eine politische oder eine mit einer solchen zusammenhängende strafbare Handlung angesehen wird (Art. 3 Ziff. 1 EAUe; vgl. auch <ref-law>).
3.1 Gemäss Art. 2 Ziff. 1 EÜBT kann der ersuchte Staat im Falle von Auslieferungsgesuchen entscheiden, dass eine schwere Gewalttat gegen das Leben, die körperliche Unversehrtheit oder die Freiheit einer Person nicht als politische oder mit einer solchen zusammen hängende Straftat angesehen wird (sofern die Tat nicht ohnehin unter Art. 1 EÜBT fällt). Analoges gilt für den Versuch, eine solche schwere Gewalttat zu begehen, oder für die Beteiligung daran als Mittäter oder Gehilfe (Art. 2 Ziff. 3 EÜBT). Keine politische Straftat im Sinne des EÜBT liegt namentlich bei schweren Straftaten vor, die in einem Angriff auf das Leben, die körperliche Unversehrtheit oder die Freiheit völkerrechtlich geschützter Personen einschliesslich Diplomaten bestehen (Art. 1 lit. c EÜBT). Das gleiche gilt für Entführungen, Geiselnahmen, schwere widerrechtliche Freiheitsentziehungen oder für Straftaten, bei deren Begehung eine Bombe, eine Handgranate, eine Rakete, eine automatische Schusswaffe oder ein Sprengstoffbrief oder -paket verwendet wird, wenn dadurch Personen gefährdet werden (Art. 1 lit. d-e EÜBT). Keine politische Straftat stellt schliesslich der Versuch dar, eine der genannten Straftaten zu begehen, oder die Beteiligung daran als Mittäter oder Gehilfe (Art. 1 lit. f EÜBT).
3.2 In der Praxis des Bundesgerichtes wird zwischen so genannt "absolut" politischen und "relativ" politischen Delikten unterschieden. "Absolut" politische Delikte stehen in unmittelbarem Zusammenhang mit politischen Vorgängen. Darunter fallen namentlich Straftaten, welche sich ausschliesslich gegen die soziale und politische Staatsorganisation richten, wie etwa Angriffe gegen die verfassungsmässige Ordnung, Landes- oder Hochverrat (<ref-ruling> E. 4.2 S. 364; <ref-ruling> E. 9b S. 578; <ref-ruling> E. 5a S. 85, je mit Hinweisen). Ein "relativ" politisches Delikt liegt nach der Rechtsprechung vor, wenn einer gemeinrechtlichen Straftat im konkreten Fall ein vorwiegend politischer Charakter zukommt. Der vorwiegend politische Charakter ergibt sich aus der politischen Natur der Umstände, Beweggründe und Ziele, die den Täter zum Handeln bestimmt haben und die in den Augen des Rechtshilferichters vorherrschend erscheinen. Das Delikt muss stets im Rahmen eines Kampfes um die Macht im Staat begangen worden sein und in einem engen Zusammenhang mit dem Gegenstand dieses Kampfes stehen (<ref-ruling> E. 4.2 S. 365; <ref-ruling> E. 9b S. 578; <ref-ruling> E. 4b S. 186 ff.; <ref-ruling> E. 5c S. 89; <ref-ruling> E. 5 S. 84 ff., je mit Hinweisen; vgl. Claude Rouiller, L‘évolution du concept de délit politique en droit de l‘entraide internationale en matière pénale, ZStrR 103/1986 S. 24 ff.; Robert Zimmermann, La coopération judiciaire internationale en matière pénale, 2. Aufl., Bern 2004, Rz. 385). Darüber hinaus müssen die fraglichen Rechtsgüterverletzungen in einem angemessenen Verhältnis zu den angestrebten Zielen stehen, und die auf dem Spiel stehenden politischen Interessen müssen wichtig und legitim genug sein, um die Tat zumindest einigermassen verständlich erscheinen zu lassen (<ref-ruling> E. 4.2 S. 365; <ref-ruling> E. 9b S. 578).
3.3 Zu denken ist hier insbesondere an den Einsatz von illegalen Mitteln gegen diktatorische oder systematisch die Menschenrechte verletzende Regimes. Bei schweren Gewaltverbrechen, namentlich Tötungsdelikten, wird der politische Charakter in der Regel verneint. Ausnahmen könnten allenfalls bei eigentlichen offenen Bürgerkriegsverhältnissen gegeben sein, oder wenn das betreffende Delikt (etwa im Falle eines "Tyrannenmordes") das einzige praktikable Mittel zur Erreichung wichtiger humanitärer Ziele darstellen würde (<ref-ruling> E. 4.2 S. 365; <ref-ruling> E. 6a S. 71 f.; vgl. Rouiller, a.a.O., S. 31; Zimmermann, a.a.O., Rz. 385 S. 431). Diese Praxis des Bundesgerichtes gilt auch bei der Prüfung der Frage, ob es sich beim Verfolgten um einen mutmasslichen Terroristen oder einen bewaffneten politischen Widerstandskämpfer handelt (vgl. <ref-ruling> E. 4 S. 363 f., E. 4.2 S. 365 mit Hinweisen; Marc Forster, Die Strafbarkeit der Unterstützung [insbesondere Finanzierung] des Terrorismus, ZStrR 121/2003 S. 423 ff., 430 f., 438 f.).
Der heiklen Unterscheidung zwischen "legitimen" Widerstandskämpfern bzw. Bürgerkriegsparteien und Terroristen hat der Eidgenössische Gesetzgeber auch beim Erlass des neuen <ref-law> (Terrorismusfinanzierung, in Kraft seit 1. Oktober 2003) Rechnung getragen. So sehen die Absätze 3 und 4 dieser Bestimmung Strafbarkeitsausschlüsse vor bei Personen, welche namentlich (das humanitäre Kriegsvölkerrecht respektierende) Bürgerkriegsparteien finanziell unterstützen oder auch Freiheitskämpfer gegen Unterdrückung und Besatzung bzw. politische Aktivisten, die zur Durchsetzung ihrer ideellen und politischen Anliegen angemessene Mittel des gewalttätigen Widerstands einsetzen (vgl. Botschaft des Bundesrates, BBl 2002 S. 5439; Kommissionspräsident Ständerat Epiney, AB 2002 S S. 1080; Ursula Cassani, Le train de mesures contre le financement du terrorisme: une loi nécessaire ? SZW 2003 S. 293 ff., 301 f.; Forster, a.a.O., S. 444 f.). Auch die Anwendung von <ref-law> (Unterstützung bzw. Beteiligung an einer terroristischen Organisation) verlangt eine analoge Abgrenzung zwischen Terroristen und politischen Widerstandskämpfern (vgl. Forster, a.a.O., S. 438 f., 445). Die vom Gesetzgeber - bewusst - an die Gerichte delegierte Aufgabe, zu bestimmen, was im Einzelfall eine straflose "politisch legitime" Gewaltanwendung darstelle und was nicht, muss allerdings als sehr delikat bezeichnet werden (vgl. Cassani, a.a.O., S. 299 f., 301 f.; Forster, a.a.O., S. 445; s. auch Botschaft, BBl 2002 S. 5439; Ständerat Pfisterer, AB StR 2002 S. 1081).
3.4 Da weder das EAUe noch das EÜBT den Begriff des politischen Deliktes näher definieren, verfügen die Vertragsstaaten hier über ein weites Ermessen. Das Bundesgericht prüft die Frage, ob ein politisches Delikt vorliegt, welches eine Auslieferung ausschliesst, mit freier Kognition (<ref-ruling> E. 4.3 S. 365; <ref-ruling> E. 9b S. 577 f.). Das schweizerische Strafrecht unterscheidet zwischen kriminellen Organisationen (<ref-law>), staatsgefährdenden rechtswidrigen Vereinigungen (<ref-law>) sowie gemeinrechtlichen Formen kollektiver Kriminalität bzw. der Teilnahme an Straftaten. Unter den Begriff der kriminellen Organisationen fallen neben den mafiaähnlichen Verbrechersyndikaten auch hochgefährliche terroristische Gruppierungen. Nicht zu den kriminellen Organisationen gezählt werden hingegen (grundsätzlich) extremistische Parteien, oppositionelle politische Gruppen sowie Organisationen, die mit angemessenen (nicht verbrecherischen) Mitteln um die politische Macht in ihrem Heimatland ringen oder einen Freiheitskampf gegen diktatorische Regimes führen (<ref-ruling> E. 4.3 S. 365 f.; <ref-ruling> E. 5c S. 574, je mit Hinweisen).
4. Nach Massgabe des EAUe sind die Vertragsparteien grundsätzlich verpflichtet, einander Personen auszuliefern, die von den Justizbehörden des ersuchenden Staates wegen einer strafbaren Handlung verfolgt oder zur Vollstreckung einer Strafe oder einer sichernden Massnahme gesucht werden (Art. 1 EAUe). Auszuliefern ist wegen Handlungen, die sowohl nach dem Recht des ersuchenden als auch nach demjenigen des ersuchten Staates mit einer Freiheitsstrafe (oder die Freiheit beschränkenden sichernden Massnahme) im Höchstmass von mindestens einem Jahr oder mit einer schwereren Strafe bedroht sind (Art. 2 Ziff. 1 EAUe; <ref-law>; vgl. <ref-ruling> E. 2.1 S. 360).
4.1 Art. 12 Ziff. 2 lit. b EAUe verlangt eine "Darstellung der Handlungen derentwegen um Auslieferung ersucht wird". Zeit und Ort ihrer Begehung sowie ihre rechtliche Würdigung unter Bezugnahme auf die anwendbaren Gesetzesbestimmungen sind "so genau wie möglich" anzugeben. Unter dem Gesichtspunkt des hier massgebenden EAUe reicht es grundsätzlich aus, wenn die Angaben im Rechtshilfeersuchen sowie in dessen Ergänzungen und Beilagen es den schweizerischen Behörden ermöglichen, zu prüfen, ob ausreichende Anhaltspunkte für eine auslieferungsfähige Straftat vorliegen, ob Verweigerungsgründe gegeben sind bzw. in welchem Umfang dem Begehren allenfalls entsprochen werden muss. Der Rechtshilferichter muss namentlich prüfen können, ob ein politisches Delikt vorliegt und ob die Voraussetzung der beidseitigen Strafbarkeit erfüllt ist. Es kann hingegen nicht verlangt werden, dass die ersuchende Behörde die Tatvorwürfe bereits abschliessend mit Beweisen belegt. Der Rechtshilferichter hat weder Tat- noch Schuldfragen zu prüfen und grundsätzlich auch keine Beweiswürdigung vorzunehmen, sondern ist vielmehr an die Sachverhaltsdarstellung im Ersuchen gebunden, soweit sie nicht durch offensichtliche Fehler, Lücken oder Widersprüche sofort entkräftet wird (vgl. <ref-ruling> E. 5b S. 257; <ref-ruling> E. 7b S. 137, 367 E. 2c S. 371, 422 E. 3c S. 431; <ref-ruling> E. 5c S. 255; <ref-ruling> E. 5b S. 121 f.; <ref-ruling> E. 5c S. 88, je mit Hinweisen).
4.2 <ref-law> bestimmt, dass das Bundesamt vom Erlass eines Auslieferungshaftbefehls absehen kann, wenn der Verfolgte ohne Verzug nachweisen kann, dass er zur Zeit der Tat nicht am Tatort war. Gemäss <ref-law> nimmt das Bundesamt die gebotenen Abklärungen vor, falls der Verfolgte behauptet, er könne ein Alibi nachweisen. In klaren Fällen wird die Auslieferung verweigert (<ref-law>). Andernfalls wird der ersuchende Staat unter Vorlage der entlastenden Beweise aufgefordert, innert kurzer Frist zu erklären, ob er das Ersuchen aufrechterhalten will (<ref-law>). Im Gegensatz zu <ref-law> sieht das hier massgebliche EAUe den Alibibeweis des Verfolgten als Auslieferungshindernis nicht ausdrücklich vor. Trotz der im EAUe verankerten grundsätzlichen Auslieferungspflicht ist der Möglichkeit eines Alibibeweises jedoch nach der Praxis des Bundesgerichtes auch im Rahmen eines gemäss Staatsvertrag durchgeführten Auslieferungsverfahrens angemessen Rechnung zu tragen. Es würde den allgemeinen Prinzipien des Auslieferungsrechtes und auch dem Verhältnismässigkeitsgebot widersprechen, einen offensichtlich Unschuldigen auszuliefern. Den Alibibeweis kann der Verfolgte allerdings nur mit dem Nachweis führen, dass er zur fraglichen Zeit überhaupt nicht am Tatort war. Dieser Nachweis ist unverzüglich und ohne Weiterungen zu erbringen (vgl. <ref-ruling> E. 2b S. 281 f.; <ref-ruling> E. 3b-c S. 281-83, je mit Hinweisen).
4.3 Die Schweiz prüft die Auslieferungsvoraussetzungen des EAUe auch im Lichte ihrer grundrechtlichen völkerrechtlichen Verpflichtungen. Nach internationalem Völkerrecht sind Folter und jede andere Art grausamer, unmenschlicher oder erniedrigender Behandlung oder Bestrafung verboten (<ref-law>, Art. 3 EMRK, Art. 7 und Art. 10 Ziff. 1 UNO-Pakt II [SR 0.103.2]). Niemand darf in einen Staat ausgeschafft werden, in dem ihm Folter oder eine andere Art grausamer und unmenschlicher Behandlung oder Bestrafung droht (<ref-law>). In Strafprozessen sind ausserdem die minimalen prozessualen Verfahrensrechte des Angeschuldigten zu gewährleisten (vgl. Art. 6 EMRK, Art. 14 UNO-Pakt II). Jeder Vertragsstaat der UNO-Folterschutzkonvention (SR 0.105) hat dafür Sorge zu tragen, dass Aussagen, die nachweislich durch Folter herbeigeführt worden sind, nicht als Beweis in einem Verfahren verwendet werden, es sei denn gegen eine der Folter angeklagte Person als Beweis dafür, dass die Aussage gemacht wurde (Art. 15 UNO-Folterschutzkonvention).
5. Das vorliegende Ersuchen ist vor folgendem historisch-politischen Hintergrund zu beurteilen. Gemäss detaillierten Berichten der UNO und der OSZE liess die damalige jugoslawisch-serbische Regierung unter dem früheren Präsidenten Slobodan Milosevic die kosovo-albanische muslimische Bevölkerung in der serbischen Provinz "Kosovo" (albanisch: Kosova) jahrelang (und besonders ab Februar 1998) terrorisieren. Die serbischen Militär- und Polizeikräfte bombardierten und zerstörten Dutzende von Dörfern, verübten zahlreiche Massaker an Zivilisten und betrieben (mit dem Ziel einer so genannten "ethnischen Säuberung" des Kosovos) systematische Massenvertreibungen der Zivilbevölkerung bzw. Deportationen, welche (bis Juni 1999) zu ca. 800'000 Flüchtlingen (etwa einem Drittel der gesamten Bevölkerung Kosovos) führten. Trotz internationalen Sanktionen und Verurteilungen durch mehrere Resolutionen des UNO-Sicherheitsrates und der OSZE stellte die serbische Regierung unter Slobodan Milosevic die völkerrechtswidrigen Kampfhandlungen im Kosovo nicht ein. Nachdem im Februar 1999 auch die Friedensverhandlungen von Rambouillet gescheitert waren, griff die NATO (ab 24. März 1999) mit Luftangriffen gegen Serbien militärisch ein.
5.1 Im Zuge des Bürgerkrieges im Kosovo und in Südserbien hatte sich auf kosovo-albanischer Seite die paramilitärische Organisation UCK (Ushtria Clirimtare e Kosovës, englisch: KLA ["Kosovo Liberation Army"]) konstituiert und an den eskalierenden Ausschreitungen und Kampfhandlungen beteiligt. In den Jahren 1998 und 1999 wehrte sich die UCK nicht zuletzt gegen den (von der UNO, der OSZE, dem Europarat und der NATO) völkerrechtlich verurteilten serbischen Staatsterror mit ebenfalls gewaltsamen Mitteln. Im Verlauf des serbisch-kosovarischen Bürgerkrieges kam es laut Berichten der UNO und der OSZE auf beiden Seiten zu Anschlägen, schweren Verbrechen und Gräueltaten, zunächst in starkem Ausmass gegen die kosovo-albanische Zivilbevölkerung, ab Mitte 1996 aber auch gegen serbische Sicherheitskräfte, Vertreter von Hilfsorganisationen und gegen die serbische Minderheit der Provinz Kosovo bzw. Südserbiens. Gemäss den Berichten der UNO und verschiedener internationaler Organisationen wurden Hunderte von albanischen Opfern von Massentötungen im Kosovo im Januar 1999 nach Serbien verfrachtet. Die Leichen wurden von serbischen Sicherheitskräften in Massengräbern verscharrt. Am 3. Juni 1999 stimmte das serbische Parlament dem Friedensplan der Regierungen der "G8" zu. Seit der Stationierung von NATO- bzw. UNO-Truppen (KFOR) im Kosovo ab Mitte Juni 1999 steht der Kosovo als "autonome" serbische Provinz unter dem Schutz und der Verwaltung der UNO (UNMIK) bzw. der OSZE (OMIK). UNO und OSZE rekrutieren, trainieren und beaufsichtigen seit Mitte 2001 auch die multiethnischen lokalen Polizeikräfte (MEP/UNMIK Police) im Kosovo.
5.2 Der frühere jugoslawische Präsident Slobodan Milosevic wurde am 28. Juni 2001 an das UNO-Tribunal (ICTY) in Den Haag überstellt und am 16. Oktober 2001 zusammen mit weiteren Angeschuldigten wegen schweren Kriegsverbrechen, namentlich begangen gegen die albanische Zivilbevölkerung im Kosovo, formell angeklagt (Fall Nr. IT-02-54). Die Anklage wurde am 29. Oktober 2001 vom ICTY zugelassen. Laut dem Bericht des Präsidenten des ICTY vom 7. Mai 2004 an den Europarat widersetzt sich die Regierung von Serbien-Montenegro seit Jahren verschiedenen UNO-Resolutionen, indem sie sich weigert, diverse angeklagte Kriegsverbrecher an den ICTY auszuliefern.
5.3 Gemäss einem bei den Rechtshilfeakten liegenden Lagebericht des US State Department vom 25. Februar 2004 erschossen serbische Polizeikräfte am 7. März 2003 zwei Mitglieder der UCK-Nachfolgeorganisation ANA ("Albanian National Army"/"Armée nationale Albanaise"). Laut serbischen Angaben seien die Erschiessungen bei einem angeblichen (fehlgeschlagenen) Bombenattentatsversuch an der südserbischen Grenze zum Kosovo erfolgt. Wie dem Bericht des US State Department weiter zu entnehmen ist, hätten am 12. März 2003 serbische nationalistische (paramilitärische) Einheiten aus dem Umfeld des ehemaligen jugoslawischen Präsidenten Slobodan Milosevic (und in Komplizenschaft mit Angehörigen der mafiaähnlichen verbrecherischen Organisation "Zemun") den damaligen serbischen Premierminister Zoran Djindjic ermordet, der auf politische Lösungen mit dem albanischen Bevölkerungsteil im Kosovo bedacht gewesen sei. Trotz gewissen Fortschritten gilt die Lage in der "autonomen Provinz Kosovo" und in Südserbien heute noch als unübersichtlich und sehr instabil. Es kommt weiterhin zu gewaltsamen Zusammenstössen und gelegentlich sogar zu Tötungsdelikten unter den verfeindeten Bevölkerungsgruppen. Auch die internationalen Organisationen haben Opfer von Anschlägen zu beklagen. Zu den letzten bürgerkriegsähnlichen Gewalttätigkeiten kam es im März 2004. Laut Berichten von UNMIK (UNO-Verwaltung im Kosovo) hätten sich an den "interethnischen" Konflikten in Kosovo bzw. Südserbien im März 2004 insgesamt rund 50'000 Personen beteiligt. Etwa 30 Personen seien dabei getötet worden. In einer Sondersitzung vom 18./19. März 2004 lehnte der UNO-Sicherheitsrat die Forderung Russlands und Serbien-Montenegros ab, den albanischen Bevölkerungsteil einseitig für die Ausschreitungen verantwortlich zu machen.
6. Im vorliegenden Fall stellt sich zunächst die Frage, inwieweit die Sachdarstellung des Ersuchens und die eher knappen Sachabklärungen des BJ es dem Bundesgericht ermöglichen, die Einrede des politischen Deliktes und die übrigen (beschwerdeweise erhobenen) Auslieferungshindernisse ausreichend zu prüfen. Die Abgrenzung zwischen "legitimen" Freiheitskämpfern bzw. Bürgerkriegsparteien und mutmasslichen Terroristen gehört zu den schwierigsten Fragen des internationalen Strafrechts ("one man's terrorist is another man's freedom fighter"; vgl. dazu Cassani, a.a.O., S. 299 f., 301 f.; Forster, a.a.O., S. 430 f., 433 f., 438 f.; Laurent Moreillon/Frédérique de Courten, La lutte contre le terrorisme et les droits du suspect, ZStrR 121/2003 S. 117 ff., 118 f.; Yves Sandoz, Lutte contre le terrorisme et droit international: risques et opportunités, RSDIE 2002 S. 319 ff., 353; Tobias Schrader, Terrorismus und das Problem seiner Definition, Kriminalistik 56/2002 S. 570 ff., 570-572). Dies gilt besonders im vorliegenden Fall bzw. vor dem Hintergrund des serbisch-kosovarischen Bürgerkrieges (vgl. dazu oben, E. 5). Die Zulässigkeit einer allfälligen Auslieferung eines angeblichen "Terroristen" an Serbien-Montenegro, dem vorgeworfen wird, er habe der kosovo-albanischen Widerstandsbewegung UCK bzw. ihren Nachfolgeorganisationen nahe gestanden und sich dabei an Straftaten gegen serbische Sicherheitskräfte beteiligt, kann nur auf der Basis von eingehenden Sachabklärungen beurteilt werden.
6.1 Im vorliegenden Fall sind höhere Anforderungen an die Verlässlichkeit und Genauigkeit des Ersuchens zu stellen als in den üblichen Fällen der Auslieferung wegen gemeinrechtlichen Straftaten (wie z.B. Drogen- oder Vermögensdelikten) ohne starke politische Konnotation und an Staaten, die keine (nur wenige Jahre zurückliegende) Bürgerkriegsgeschichte zu bewältigen haben. Zwar weist das BJ darauf hin, dass das Bundesgericht bereits im Jahre 2003 eine Auslieferung an Serbien und Montenegro bewilligt habe. Beim zitierten Entscheid handelte es sich allerdings um die Auslieferung eines rechtskräftig verurteilten mehrfachen Vergewaltigers (Urteil 1A.159/2003 vom 15. September 2003). Im Rahmen der Rechtshilfevoraussetzung der beidseitigen Strafbarkeit muss die Sachdarstellung des Ersuchens namentlich die Prüfung ermöglichen, ob sich die Ermittlungen wegen angeblich "terroristischer" Umtriebe gegen eine terroristische Organisation im Sinne von <ref-law> richten (vgl. <ref-ruling> E. 2.2-2.6 S. 360-363). Der vorliegende Fall verlangt aber auch die Ausleuchtung des politischen und völkerrechtlich-humanitären Kontextes. Weder darf die internationale Rechtshilfe in Strafsachen zu politischen Zwecken missbraucht werden, noch dürfen Hinweise auf den angeblich politischen Charakter einer Strafverfolgung dazu führen, dass Schwerkriminelle oder Terroristen von Strafverfolgung verschont bleiben.
6.2 Im angefochtenen Entscheid wird die Sachverhaltsdarstellung des Ersuchens wie folgt zusammengefasst: In den Jahren 1999-2000 bzw. ab 2002 habe der Verfolgte den "terroristischen Organisationen" OVPMB bzw. ANA ("Albanian National Army"/"Armée nationale albanaise") angehört. Mit den Mitgliedern dieser Organisationen habe er "einen ständigen Telefonkontakt aufrecht erhalten" und "vor allem eine beratende Rolle gespielt". Ausserdem habe er "seine Gesprächspartner zur Ausführung konkreter terroristischer Aktionen gegen Angehörige des Sicherheitsdienstes in Südserbien angestiftet und diese Aktionen vorbereitet bzw. koordiniert". Auch sei der Verfolgte "für die Bereitstellung von Geldmitteln zur Beschaffung von Ausrüstung sowie Waffen und Munition zuständig gewesen". Am 3. Februar 2003 habe die Organisation ANA "in Serbien einen Sicherheitsbeamten getötet". Die Täter hätten sich "danach im Haus des Verfolgten versteckt". Mitglieder der ANA hätten ausserdem am 2. März und 23. September 2003 "in Serbien Sprengkörper an verschiedenen Orten angebracht, welche in der Folge nicht explodiert" seien (angefochtener Entscheid, S. 3 Ziff. 4). Dem Verfolgten werde allerdings "keine direkte Tatbeteiligung" an konkreten terroristischen Straftaten vorgeworfen (angefochtener Entscheid, S. 7 in fine).
6.3 Gemäss dem Auslieferungsersuchen des serbischen Ministeriums für Menschen- und Minderheitenrechte vom 15. Januar 2004 führt das Bezirksgericht in Vranje ein Strafverfahren gegen den Verfolgten wegen "des Verdachts der Straftat der Vereinigung zu feindlichen Tätigkeiten (...) in Verbindung mit der Straftat des Terrorismus". Das Ersuchen vom 15./23. Januar 2004 enthält keinerlei Angaben zum inkriminierten Sachverhalt. Einerseits wird dargelegt, dass es sich beim Verfolgten um einen Tatverdächtigen handle und dass das Bezirksgericht in Vranje gegen ihn "Ermittlungen" eingeleitet und "Untersuchungshaft" angeordnet habe. Anderseits wird ausgeführt, der Verfolgte sei "für eine Straftat verurteilt" worden, "für die" im EAUe "eine Auslieferungspflicht vorgesehen ist". Das Auslieferungsersuchen sei "zur Beendigung des eingeleiteten Strafverfahrens und zur Vollstreckung der über ihn eventuell verhängten Strafe begründet und gerechtfertigt". Dem Ersuchen liegt kein Strafurteil bei; ihm beigefügt sind Beschlüsse des Bezirksgerichtes Vranje betreffend die Einleitung einer Strafuntersuchung, die Anordnung von Untersuchungshaft und den Erlass einer Verhaftsausschreibung. Auch in den übrigen Akten findet sich kein Strafurteil im Sinne von Art. 2 Ziff. 1 (zweiter Satz) EAUe. Das Ersuchen erfolgt im Hinblick auf eine hängige Strafuntersuchung.
6.4 Im Beschluss des Ermittlungsrichters des Bezirksgerichtes Vranje vom 2. Oktober 2003 wird dem Verfolgten und weiteren acht Angeschuldigten "Vereinigung zu feindlichen Tätigkeiten", "unerlaubte Beschaffung und Halten von Schusswaffen und Sprengstoff" sowie "Missbrauch der Amtsgewalt" vorgeworfen. Bei sämtlichen Angeschuldigten handelt es sich um ethnische Albaner. Bei vier Mitangeschuldigten handelt es sich um Polizisten der so genannten "multiethnischen" Sicherheitskräfte (MEP) in Südserbien.
Der inkriminierte Sachverhalt wird wie folgt dargestellt: Die Angeschuldigten seien 1999-2000 "aktive Mitglieder der terroristischen Organisation OVPMB" und im Jahr 2002 "wieder Angehörige der terroristischen Organisation ANA" gewesen. Die genannten Organisationen seien "zur Gefährdung der Verfassungsordnung und Sicherheit der Bundesrepublik Jugoslawien - jetzt Serbien und Montenegro - gegründet" worden. Die Angeschuldigten hätten das "Programm und die Ziele der Front der nationalen Vereinigung der Albaner" unterstützt. Dem Verfolgten wird vorgeworfen, er sei einer der "Organisatoren" und für die "Beschaffung von Waffen, Munition, Militärausstattung und Geld für terroristische Tätigkeiten" zuständig gewesen. Zwei der Mitangeschuldigten hätten am 3. Februar 2003 in Bujanovac einen serbischen Sicherheitsbeamten erschossen. Ein dritter Mitangeschuldigter habe den Tätern dabei geholfen, "indem er sie im Haus des" Verfolgten "unterbrachte und am nächsten Tag durch Waldwege über die Verwaltungsgrenze" in den Kosovo transportierte. Mitangeschuldigte hätten sodann am 2. März 2003 "auf dem Weg Lucane-Turija" einen "Sprengkörper" angebracht, der "nicht explodiert" sei. Am 23. September 2003 habe ein Mitangeschuldigter einem Minderjährigen einen selbst hergestellten "Sprengkörper" übergeben. Letzterer habe erfolglos versucht, den Sprengkörper in einer Mittelschule in Bujanovac zu zünden.
6.5 Am 27. Januar 2004 machte das BJ die serbischen Behörden darauf aufmerksam, dass die Sachdarstellung unzureichend sei. Sie wurden aufgefordert, ergänzende Informationen zu den konkreten strafbaren Handlungen bzw. Tatbeiträgen zu übermitteln, die dem Verfolgten persönlich vorgeworfen werden.
Das ergänzende Ersuchen vom 9. Februar 2004 enthält eine Stellungnahme des zuständigen Ermittlungsrichters vom 3. Februar 2004. Danach verfügen die serbischen Behörden "zurzeit über keine Angaben" zu den Aktivitäten des Verfolgten in den Jahren 1999-2000 sowie 2002. Auch was die "konkrete Rolle" des Verfolgten als Mitglied der der ANA im Jahre 2003 betrifft, habe "die bisherige Ermittlung keine zuverlässigen diesbezüglichen Angaben" zutage gefördert. Insbesondere sei nicht bekannt, welchen konkreten Tatbeitrag der Verfolgte beim untersuchten Tötungsdelikt vom 3. Februar 2003 geliefert hätte. Das gleiche gelte für "den Aufbau und die Struktur" der Organisationen OVPMB und ANA; diesbezüglich seien keine zuverlässigen Informationen vorhanden. Der Verfolgte habe "vor allem eine beratende Rolle" inne gehabt und "ständigen Telefonkontakt" zu den Mitangeschuldigten aufrecht erhalten. Ausserdem habe er sich für das Bereitstellen von Geldmitteln bzw. für die Beschaffung von Ausrüstung, Waffen und Munition "eingesetzt". Nähere Einzelheiten dazu werden nicht genannt. Dies gilt auch für die Zeitpunkte oder Inhalte der telefonischen Kontakte.
In einer weiteren Stellungnahme vom 18./22. März 2004 machen die serbischen Behörden ("Ministerium für Menschen- und Minderheitenrechte") schliesslich Folgendes geltend: Die Befreiungsarmee Kosovos (UCK) sei nach Ankunft der internationalen Friedenstruppen "angeblich aufgelöst" worden, "obwohl fast alle Mitglieder in das 'Kosovo Schutzkorps' aufgenommen wurden". "Das Pendant" zur UCK "in Südserbien" sei "die 'OVPMB' und in Mazedonien die 'ONA'". "Das Wesen" der Nachfolgeorganisationen sei "gleich". Sie betrieben "den gewaltsamen Anschluss aller von Albanern bewohnten Gebieten" Serbiens "an die Republik Albanien und die Gründung des 'Gossalbanien'". Die telefonische Kommunikation zwischen dem Verfolgten und Mitgliedern der ANA habe "im Zeitraum von Januar bis September 2003" stattgefunden. Aus der Abhörung von Telefongesprächen gehe hervor dass der Verfolgte über den Plan der "am 04.02.2003" (recte wohl: 03.02.04) erfolgten Tötung eines serbischen Polizeibeamten informiert gewesen sei. Einer der Täter habe vor der Tötung per SMS mitgeteilt, sie gingen, "den Freund zu verheiraten". Nach der Tat sei ein weiteres SMS abgeschickt worden mit dem Inhalt: "wir haben ihn verheiratet". Der Verfolgte habe in diesem Zusammenhang noch weitere Informationen erhalten. Auch über den Plan, eine "Panzermine" zu legen auf einer Strasse, die von Angehörigen der serbischen Sicherheitskräfte benutzt worden sei, habe der Verfolgte Kenntnis gehabt. Bei der Verhinderung des Anbringens eines "Sprengkörpers" hätten serbische Sicherheitskräfte am 7. März 2003 zwei albanische Täter erschossen. Am 23. September 2003 sei ein Major der serbischen Armee durch Schüsse von albanischen Tätern schwer verletzt worden. Als Koordinator des "Albanischen Nationalfonds" habe der Verfolgte Gelder für die ANA gesammelt. Am Telefon sei auch über Waffen gesprochen worden.
6.6 Zur Einrede des politischen Deliktes und zum Umfang der zulässigen Rechtshilfe äussert sich das BJ wie folgt: Nach Auffassung des BJ gehören die fraglichen kosovo-albanischen Organisationen (OVPMB und ANA) "wie z.B. auch die 'Brigate Rosse' oder die 'ETA' zu den kriminellen terroristischen Organisationen und nicht zu Gruppierungen, die sich mit angemessenen - oder zumindest noch vertretbaren - Mitteln am Kampf um die politische Macht in ihrer Heimat beteiligen" (angefochtener Entscheid, S. 9). "Aufgrund der notorisch auch politisch motivierten Aktivitäten solcher Organisationen" sei im vorliegenden Fall "bei der Bewilligung der Auslieferung ein Vorbehalt anzubringen, wonach die serbischen Behörden in Bezug auf den Verfolgten keine Strafverfolgung durchführen dürfen, soweit die Mitgliedschaft bei den fraglichen Organisationen auch einen politischen Zweck verfolgt". "Die serbischen Behörden dürfen somit den Verfolgten wegen allfälliger politischer Hintergründe der fraglichen Straftaten nicht verfolgen oder bestrafen, auch nicht in der Form einer Erhöhung oder Verschärfung einer allfälligen Strafe für diejenigen Delikte, für welche die Auslieferung bewilligt wird" (angefochtener Entscheid, S. 5 Ziff. 4 in fine).
6.7 Zur Frage der beidseitigen Strafbarkeit erwägt das BJ Folgendes: Die fraglichen Organisationen (OVPMB und ANA) seien "Nachfolgeorganisationen der albanischen Befreiungsarmee von Kosovo (UCK) und eng miteinander verbunden". "Bei ihren Mitgliedern" handle es sich "häufig um dieselben Personen". "Nach der Auflösung der OVPMB im Mai 2001" seien "die meisten Mitglieder" der ANA beigetreten. Die ANA betreibe "Untergrundaktivitäten" und verübe "Anschläge, namentlich gegen serbische Sicherheitskräfte in Südserbien". Seit 2001 seien in der Krisenregion ca. 25 serbische Sicherheitsbeamte getötet worden. Die ANA sei auch für andere Straftaten verantwortlich (wie Schutzgelderpressungen, Schmuggel, Waffen- und Drogenhandel usw.). Politiker der US-Regierung sowie der ehemalige Chef der UNO-Verwaltung im Kosovo hätten die ANA als terroristisch bezeichnet. Das Verhalten des Verfolgten falle unter den Tatbestand von <ref-law>. Er sei "mit den anderen Mitgliedern der Organisation in ständigem Kontakt gestanden" und habe "diese namentlich beraten und deren Handlungen sogar beeinflusst" bzw. sie "zu konkreten terroristischen Aktionen angestiftet". Ob dieses Verhalten als Beteiligung an oder Unterstützung einer terroristischen Organisation anzusehen sei "oder ob allenfalls noch andere schweizerische Strafbestimmungen zur Anwendung kommen könnten", könne "demnach offen bleiben" (angefochtener Entscheid, S. 4 f. Ziff. 4).
6.8 Zur Frage des Alibibeweises äussert sich das BJ wie folgt: Zwar habe der Verfolgte für die "konkret angegebenen Tatzeiten im Jahre 2003" Alibis angegeben; insbesondere habe er sich damals nicht in Südserbien, sondern an seinem Wohn- und Arbeitsort in der Schweiz aufgehalten. Die serbischen Behörden, die auf diese Alibihinweise aufmerksam gemacht worden seien, hätten jedoch das Auslieferungsersuchen nicht zurückgezogen. "Selbst wenn die vom Verfolgten eingereichten Unterlagen als Alibibeweise im Sinne des IRSG anzusehen wären", komme eine Verweigerung der Auslieferung "nicht in Frage", da sich die Alibiangaben "nur auf einen Teil des Auslieferungsersuchens" bezögen. Der Verfolgte habe "nicht unbedingt direkt in Serbien und Montenegro" gehandelt (angefochtener Entscheid, S. 7).
Ebenso wenig drohe dem Verfolgten in Serbien eine menschenrechtswidrige Behandlung. Zwar mache er geltend, dass ihm als ethnischem Albaner "und unter Berücksichtigung der ihm zur Last gelegten Delikte eine schwerwiegende Verletzung der Menschenrechte" drohe. "Konkrete, auf seine Person bezogene Aussagen" könne er "indessen nicht vorbringen". "Auch aus den Auslieferungsunterlagen" liessen sich "keine diesbezüglichen Angaben entnehmen". "Dass ein im serbischen Strafverfahren in dieser Sache Mitangeschuldigter geltend gemacht hat, er sei von der Polizei misshandelt worden", weise "ebenfalls nicht darauf hin". Dies zeige vielmehr, dass "solche Vorkommnisse" in Serbien "ernst genommen" würden. Serbien und Montenegro seien "Mitglied des Europarates" und hätten kürzlich "die EMRK unterschrieben". Ausserdem habe das Bundesgericht bereits im erwähnten Urteil 1A.159/2003 vom 15. September 2003 die Auslieferung eines (rechtskräftig verurteilten) serbischen Staatsangehörigen nach Serbien und Montenegro (wegen mehrfacher Vergewaltigung) bewilligt (angefochtener Entscheid, S. 8 lit. b).
7. Es fragt sich, ob ausreichend abgeklärt ist, in welchem speziellen Kontext die Tatvorwürfe gegen den Verfolgten stehen.
7.1 Bei den Opfern der als "terroristisch" eingestuften "Untergrundaktionen" und Anschläge der ANA handelt es sich (nach Darstellung des Ersuchens) in erster Linie um Angehörige der serbischen Polizei- und Militärstreitkräfte in Südserbien. Angeschuldigt werden von serbischer Seite primär kosovo-albanische Sicherheitskräfte Südserbiens bzw. der "autonomen Provinz" Kosovo, nämlich Angehörige der von UNO/UNMIK, OSZE/OMIK und NATO/KFOR ab Mai 2001 eingesetzten und überwachten "multiethnischen" Polizei (MEP/"UNMIK Police"), die überwiegend aus ethnischen Albanern und teilweise auch aus Serben zusammengesetzt ist. Unbestrittenermassen sind vier der Mitbeschuldigten Angehörige der "multiethnischen" Polizeikräfte. Vor diesem Hintergrund stellt sich die Frage, inwieweit die ehemaligen Bürgerkriegsparteien (kosovo-albanischer Widerstand und kosovarische Polizei sowie serbische Sicherheitskräfte) und deren Nachfolgeorganisationen sich gegenseitig gewaltsamer bzw. "terroristischer" Aktivitäten im südserbischen Krisengebiet bezichtigen.
Aber auch bei der Prüfung der beidseitigen Strafbarkeit bleiben wesentliche Fragen offen. So ist nicht ausreichend abgeklärt, ob die Organisationen, die der Verfolgte angeblich unterstützte bzw. denen er angehört haben soll (1999-2000 OVPMB bzw. UCPMB, ab 2002 ANA) aufgrund von verlässlichen Informationen überhaupt als "terroristisch" eingestuft werden können. Trotz entsprechenden Nachfragen des BJ haben die serbischen Behörden keine Informationen zum Aufbau und zur Struktur der Organisationen OVPMB und ANA vorgelegt. Nach Angaben des Bundesamtes für Polizei (Dienst für Analyse und Prävention) hat die ANA "keine einheitliche militärisch-operative Führung". Über die Strukturen der OVPMB "liegen keine gesicherten Erkenntnisse vor". Die ursprüngliche UCK kann kaum als "terroristisch" bezeichnet werden, zumal es sich dabei unbestrittenermassen um eine völkerrechtlich anerkannte Bürgerkriegspartei handelte. Namentlich war die Führung der UCK (zusammen mit anderen Repräsentanten der kosovo-albanischen Bevölkerung) als offizielle Verhandlungspartei an den (fehlgeschlagenen) Friedensgesprächen von Rambouillet im Februar 1999 beteiligt. Auch die Gleichstellung der Nachfolgegruppierungen OVPMB und ANA mit terroristischen Organisationen wie den italienischen "Brigate Rosse" oder der baskischen ETA erscheint problematisch. Zwar verweist das BJ auf einen Bericht des Bundesamtes für Polizei, wonach Politiker der US-Regierung und ein ehemaliger Leiter der UNO-Verwaltung im Kosovo die Nachfolgeorganisation ANA angeblich als "terroristisch" bezeichnet hätten. Es sind zu diesen Fragen jedoch keine Berichte der zuständigen internationalen Gremien (UNO, OSZE, ICTY) bzw. von deren Terrorismusexperten beigezogen worden, welche z.B. über die zuständigen Dienste des EDA eingeholt werden könnten. Verlässliche Informationen zur Struktur und zum Aufbau von OVPMB und ANA liegen wie erwähnt nicht vor.
7.2 Näher zu prüfen ist, ob die Vorwürfe gegen den Verfolgten politisch motiviert sein könnten und ob sie die Beurteilung der beidseitigen Strafbarkeit erlauben.
Die im Ersuchen dargelegten Anhaltspunkte dafür, dass es sich bei den fraglichen albanischen Gruppierungen um terroristische Organisationen im Sinne des schweizerischen und internationalen Strafrechts handelt, müssen als vage bezeichnet werden. Wie bereits erwähnt, handelt es sich bei den Hauptbetroffenen der als "terroristisch" eingestuften Untergrundaktionen und Anschläge der ANA nach Darstellung des Ersuchens um serbische Sicherheitskräfte. Angeschuldigt werden von serbischer Seite vorwiegend kosovo-albanische Sicherheitskräfte, nämlich Angehörige der ab 2001 von UNMIK und OSZE eingesetzten "multiethnischen" Polizei (MEP). Vier der Mitbeschuldigten (bzw. die Hauptangeschuldigten) sind unbestrittenermassen Angehörige dieser multiethnischen Polizeikräfte. Gemäss dem bei den Akten liegenden Kosovo-Bericht des U.S. State Department vom 25. Februar 2004 sei es vor allem der Einsetzung der "multiethnischen" Polizei zu verdanken, dass es ab 2002 zu einer starken Abnahme von Übergriffen der (ehemals serbischen) Polizei gegen ethnische Albaner in Südserbien gekommen ist. Bei der vorliegenden Strafuntersuchung stehen sich somit faktisch die ehemaligen Bürgerkriegsparteien gegenüber.
7.3 Dem Verfolgten wird sodann keine direkte Tatbeteiligung an konkreten terroristischen Straftaten vorgeworfen (vgl. auch angefochtener Entscheid, S. 7 in fine). Vielmehr habe ein Mitbeschuldigter die Polizistenattentäter am 3. Februar 2003 für einen Tag im Haus des Verfolgten "untergebracht". Unklar erscheint auch, ob das betreffende Haus sich in Bujanovac oder in Veliki Trnovac befindet. Dem Verfolgten wird zwar die logistische Unterstützung der albanischen Organisationen OVPMB und ANA vorgeworfen. Nähere Informationen dazu sind jedoch gemäss den Angaben der serbischen Behörden nicht vorhanden. Dies gilt namentlich für die Art und Weise, die Umstände oder die Zeitpunkte der mutmasslichen Beschaffung von Geldmitteln und Waffen. Die vagen und teilweise widersprüchlichen Angaben im Ersuchen und dessen Ergänzungen kontrastieren mit den Medienmitteilungen der serbischen Regierung, wonach es sich beim (mit vollem Namen genannten) Verfolgten um den "main financier" und "mastermind of terrorism in Southern Serbia" handle. Sachdienliche Angaben dazu oder zum persönlichen, beruflichen und politischen Umfeld des Verfolgten bzw. zu seinem Werdegang und Verhalten in seiner Heimat und in der Schweiz enthält auch der angefochtene Entscheid nicht. Ebenso wenig wurden Informationen (etwa bei der UNMIK/OMIK) über die Hauptangeschuldigten eingeholt, bei denen es sich unbestrittenermassen um Angehörige der MEP handle.
7.4 Art. 12 Ziff. 2 lit. b EAUe bestimmt, dass Zeit, Ort und Umstände der Begehung der fraglichen Delikte "so genau wie möglich" anzugeben seien (vgl. oben, E. 4.1). Im vorliegenden Fall weisen die dem Verfolgten vorgeworfenen Delikte zweifelsohne einen politischen Konnex auf. Es sind daher erhöhte Anforderungen an die Ausführlichkeit, Widerspruchsfreiheit und Verlässlichkeit des Ersuchens zu verlangen. Zum einen erscheint dies erforderlich, damit die Einrede des politischen Deliktes sachgerecht beurteilt werden kann (vgl. oben, E. 3). Zum andern sind nähere verlässliche Angaben notwendig, um - im Falle einer Auslieferung - gegenüber dem ersuchenden Staat genau festlegen zu können, für welche Straftaten die Auslieferung erfolgt (vgl. <ref-ruling> E. 2.2-2.6 S. 360-363).
Das vorliegende Ersuchen und seine (sich teilweise widersprechenden) Ergänzungen genügen diesen Anforderungen nicht. Dieser Mangel kann nicht dadurch wettgemacht werden, dass die Auslieferung mit dem Hinweis versehen wird, die serbischen Behörden dürften den Verfolgten wegen allfälliger politischer Hintergründe nicht verfolgen oder bestrafen. Ohne ausreichende Abklärungen zum Sachverhalt ist es im vorliegenden kontroversen Fall nicht möglich, die Einrede des politischen Deliktes zu beurteilen (vgl. <ref-ruling> E. 4.2 S. 365, E. 4.3 S. 365 f.). Ebenso wenig kann geprüft werden, inwieweit hier das Rechtshilfeerfordernis der beidseitigen Strafbarkeit erfüllt ist. Dies gilt namentlich für die Tatbestandsmerkmale von <ref-law> (vgl. <ref-ruling> E. 2.2-2.6 S. 360-363) oder <ref-law> (vgl. dazu Forster, a.a.O., S. 443 ff.).
7.5 Im vorliegenden Fall bedürfte auch die Frage des Alibis (vgl. oben, E. 4.2) weiterer Abklärungen. Im Ersuchen wird dem Verfolgten die Beteiligung an "terroristischen" Aktivitäten in Südserbien im Zeitraum von 3. Februar bis 9. März 2003 bzw. 23. September 2003 vorgeworfen. Wie im angefochtenen Entscheid eingeräumt wird, hat der Verfolgte diesbezüglich Alibis geltend gemacht und dokumentiert. Insbesondere will er sich an den fraglichen Daten nicht in Serbien, sondern nachweisbar an seinem Wohn- und Arbeitsort in der Schweiz aufgehalten haben. Das BJ verweist darauf, dass die serbischen Behörden über die Alibihinweise "informiert" worden seien; "ein Rückzug des Auslieferungsersuchens" sei jedoch nicht erfolgt. Das BJ vertritt die Auffassung, selbst wenn sie zuträfen, änderten die Alibis nichts an der Zulässigkeit der Auslieferung, da sie sich nicht auf sämtliche Anklagepunkte bezögen.
Diese Argumentation greift zu kurz. Alibis für die Tatvorwürfe im Jahre 2003 könnten zumindest zu einer Begrenzung der Rechtshilfe (auf die allfälligen verbleibenden Anklagepunkte) führen. Im Übrigen ist aufgrund der vorliegenden Akten darauf hinzuweisen, dass bei einem Wegfall der Tatvorwürfe betreffend das Jahr 2003 nur noch sehr vage und strafrechtlich kaum qualifizierbare Vorwürfe gegen den Verfolgten übrig blieben. Nähere Angaben zur angeblichen logistischen Unterstützung (Art und Weise - insbesondere Zeitpunkte und Bezugskanäle - der Beschaffung von Geld und Waffen) werden im Ersuchen und dessen Ergänzungen nicht gemacht. Die ersuchende Behörde hat demgegenüber das Protokoll der untersuchungsrichterlichen Einvernahme eines Mitangeschuldigten vom 1. Oktober 2003 eingereicht. Danach habe es sich beim Verfolgten "sicher nicht" um ein Mitglied der ANA gehandelt.
7.6 Schliesslich ist auch auf alarmierende Berichte des UNHCR, der OSZE und von diversen Menschenrechtsorganisationen aus den Jahren 2003 und 2004 hinzuweisen über verschiedene Fälle von menschenrechtswidriger erniedrigender Behandlung durch serbische Polizeikräfte, namentlich gegen inhaftierte mutmassliche kosovo-albanische Nationalisten und Extremisten. Aus dem Rechtshilfedossier ergeben sich sodann ernsthafte Anhaltspunkte für die Befürchtung, dass im vorliegenden Fall Mitbeschuldigte des Verfolgten im serbischen Polizeigewahrsam massiv misshandelt wurden. Daher ist die Menschenrechtslage in Serbien und Montenegro - im Hinblick auf die politische Relevanz der erhobenen Tatvorwürfe - näher abzuklären.
7.7 Nach dem Gesagten können aufgrund des Ersuchens und der vorliegenden Akten weder die Einrede der politischen Verfolgung noch die übrigen geltend gemachten Auslieferungshindernisse ausreichend geprüft werden. Dies gilt namentlich für die Rechtshilfevoraussetzung der beidseitigen Strafbarkeit. Was die Einrede des politischen Deliktes betrifft, so hat zwar das Bundesgericht erstinstanzlich darüber zu entscheiden. Es ist jedoch nicht Aufgabe des Bundesgerichtes, in Auslieferungsfällen die notwendigen Sachabklärungen selber zu treffen. Auch in Fällen, bei denen Einreden des politischen Delikts erfolgen oder sich bei der Instruktion entsprechende Fragen stellen, hat daher das zuständige BJ tatsächliche Abklärungen hinsichtlich aller Auslieferungsvoraussetzungen vollumfänglich vorzunehmen (vgl. <ref-ruling> E. 1.1.2 S. 358). Wie sich aus den vorstehenden Erwägungen ergibt, drängen sich im vorliegenden Fall weitere Sachabklärungen auf.
Die Beschwerde ist daher gutzuheissen und der angefochtene Entscheid aufzuheben. Auf den Antrag des BJ, es sei die Einrede des politischen Deliktes abzuweisen, kann zurzeit nicht eingetreten werden. Das Rechtshilfedossier ist zu ergänzenden Sachverhaltsabklärungen, zur Neubeurteilung (betreffend Auslieferungsvoraussetzungen) und zur neuen Antragstellung (betreffend die Einrede des politischen Delikts) an das BJ zurückzuweisen.
8. Der Verfolgte stellt ein Haftentlassungsgesuch. Während der hängigen Beschwerde gegen den Auslieferungsentscheid ist grundsätzlich das Bundesgericht zur Prüfung des Haftentlassungsgesuches zuständig (vgl. <ref-ruling> E. 1.2 S. 359 mit Hinweis).
Die blosse Aufhebung des angefochtenen Auslieferungsentscheides und die Rückweisung der Streitsache (zu näheren Abklärungen und zur Neuentscheidung bzw. neuen Antragstellung) führt nicht automatisch zur Entlassung des Verfolgten aus der Auslieferungshaft. Das Bundesgericht stellt im vorliegenden Urteil lediglich fest, dass es nicht in der Lage ist, auf der Basis der vorliegenden Akten die Einrede des politischen Deliktes bzw. die materiellen Auslieferungsvoraussetzungen zu prüfen. Daraus allein folgt noch nicht die Unrechtmässigkeit der Auslieferungshaft. Weder bestreitet der Verfolgte das Vorliegen von ausreichenden Haftgründen, noch bringt er andere Einwände gegen die Rechtmässigkeit der Auslieferungshaft vor. Soweit er lediglich die materiellen Auslieferungsvoraussetzungen bestreitet bzw. die Einrede der politischen Verfolgung erhebt, begründet er keine Haftentlassungsgründe. Das Haftentlassungsgesuch ist daher abzuweisen.
9. Zusammenfassend ergibt sich, dass die Beschwerde gutzuheissen, der angefochtene Entscheid aufzuheben und die Streitsache zur Neubeurteilung an das BJ zurückzuweisen ist. Auf den Antrag des BJ, es sei die Einrede des politischen Deliktes abzuweisen, kann zurzeit nicht eingetreten werden. Das Haftentlassungsgesuch ist abzuweisen.
Dem Ausgang des Verfahrens entsprechend, sind keine Gerichtskosten zu erheben (Art. 156 Abs. 2 OG). Dem anwaltlich vertretenen Beschwerdeführer und Antragsgegner ist hingegen eine angemessene Parteientschädigung zuzusprechen (Art. 159 OG).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird gutgeheissen, der angefochtene Entscheid des Bundesamtes für Justiz vom 7. April 2004 wird aufgehoben, und die Streitsache wird zur Neubeurteilung an das Bundesamt für Justiz zurückgewiesen (Verfahren 1A.116/2004).
2. Auf den Antrag des Bundesamtes für Justiz vom 7. April 2004, es sei die Einrede des politischen Deliktes abzuweisen, wird nicht eingetreten (Verfahren 1A.80/2004).
3. Das Haftentlassungsgesuch wird abgewiesen.
4. Es werden keine Kosten erhoben. Das Bundesamt für Justiz hat dem Beschwerdeführer und Antragsgegner eine Parteientschädigung von Fr. 3'000.-- zu entrichten.
5. Dieses Urteil wird dem Beschwerdeführer und Antragsgegner sowie dem Bundesamt für Justiz, Abteilung Internationale Rechtshilfe, Sektion Auslieferung, schriftlich mitgeteilt.
Lausanne, 8. Juli 2004
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: