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. Dagegen gelangte X._ mit Verwaltungsgerichtsbeschwerde vom 5. Mai 2004 an das Bundesgericht (Verfahren 1A.116/2004). 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). Mit Urteil vom 8. Juli 2004 hiess das Bundesgericht die Verwaltungsgerichtsbeschwerde gut; der Auslieferungsentscheid des BJ vom 7. April 2004 wurde aufgehoben, und die Streitsache wurde zur Neubeurteilung an das BJ zurückgewiesen (Verfahren 1A.116/2004). Auf den Antrag des BJ vom 7. April 2004, es sei die Einrede des politischen Deliktes abzuweisen, trat das Bundesgericht nicht ein (Verfahren 1A.80/2004). Das Haftentlassungsgesuch des Verfolgten wies das Bundesgericht ab. Das Urteil vom 8. Juli 2004 wurde in <ref-ruling> teilweise publiziert.
C. Am 13./14. August sowie am 17. September 2004 reichte die Botschaft von Serbien und Montenegro Gesuchsergänzungen ein. Am 13. August und 9. September 2004 übermittelten der Dienst für Analyse und Prävention des Bundesamtes für Polizei sowie das Eidgenössische Departement für auswärtige Angelegenheiten dem BJ Zusatzberichte. Mit Entscheid vom 3. Dezember 2004 bewilligte das BJ erneut die Auslieferung des Verfolgten an Serbien und Montenegro. Der Auslieferungsentscheid erfolgte "unter dem Vorbehalt des bundesgerichtlichen Entscheids über die Einsprache des politischen Delikts".
D. Mit separater Eingabe vom 3. Dezember 2004 stellte das BJ beim Bundesgericht den Antrag, die Einrede des Verfolgten, wonach er politisch verfolgt werde, sei abzulehnen (Verfahren 1A.288/2004). Zur Begründung verweist das BJ auf die Erwägungen des gleichentags erfolgten Auslieferungsentscheides. Der Verfolgte hält mit Stellungnahme vom 22. Dezember 2004 an der Einrede des politischen Deliktes fest und beantragt im Hauptstandpunkt die Abweisung des Auslieferungsersuchens und die Entlassung aus der Haft. Am 30. Dezember 2004 hat das BJ auf eine Vernehmlassung (im Verfahren 1A.288/2004) verzichtet.
E. Gegen den Auslieferungsentscheid des BJ vom 3. Dezember 2004 gelangte X._ mit Verwaltungsgerichtsbeschwerde vom 4. Januar 2005 an das Bundesgericht (Verfahren 1A.4/2005). Er beantragt im Hauptstandpunkt die Abweisung des Auslieferungsersuchens und die Entlassung aus der Haft. Das BJ verzichtete am 12. Januar 2005 ausdrücklich auf eine Vernehmlassung (im Verfahren 1A.4/2005). Der Beschwerdeführer reichte am 21. Januar und 24. Februar 2005 (unaufgefordert) weitere Eingaben beim Bundesgericht ein.

Das Bundesgericht zieht in Erwägung:
1. Zu den Eintretensvoraussetzungen und weiteren verfahrensrechtlichen Fragen kann auf die Erwägungen von <ref-ruling> E. 1 S. 339-341 verwiesen werden.
2. Der Beschwerdeführer macht zunächst geltend, das Ersuchen und seine diversen Ergänzungen seien ungenügend, fehlerhaft und widersprüchlich. Auch gestützt auf die neu eingeholten Berichte blieben die gegen ihn erhobenen Tatvorwürfe "nach wie vor im Dunkeln"; es würden "weder Begehungsdaten noch konkrete Delikte genannt". Bei der "angeblichen SMS- sowie Audio-Kommunikation" des Beschwerdeführers mit Hauptverdächtigen handle es sich um eine "pure Behauptung" der ersuchenden Behörde. Es fehle sodann an der Voraussetzung der beidseitigen Strafbarkeit. Die Tatvorwürfe gingen "über ein strafloses Gutheissen von Delikten nicht hinaus". Auch der Tatbestand von Art. 260ter Ziff. 1 StGB sei nicht erfüllt. Die zusätzlichen Abklärungen der eidgenössischen Behörden hätten den Vorwurf, dass die ANA eine terroristische Organisation im strafrechtlichen Sinne sei, nicht erhärtet. Ausserdem könne die ANA "nicht in Verbindung mit dem Verfolgten gebracht werden".
2.1 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; Art. 35 Abs. 1 IRSG; vgl. <ref-ruling> E. 2.1 S. 360).
2.2 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. für welche mutmasslichen Delikte 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).
2.3 Art. 47 Abs. 1 lit. b IRSG 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 Art. 53 Abs. 1 IRSG 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 (Art. 53 Abs. 2 Satz 1 IRSG). Andernfalls wird der ersuchende Staat unter Vorlage der entlastenden Beweise aufgefordert, innert kurzer Frist zu erklären, ob er das Ersuchen aufrechterhalten will (Art. 53 Abs. 2 Satz 2 IRSG). Im Gegensatz zu Art. 53 IRSG 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).
2.4 Das vorliegende Auslieferungsersuchen ist vor folgendem historisch-politischen Hintergrund zu beurteilen:
2.4.1 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.
-:-
-:-
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, später aber auch gegen serbische Sicherheitskräfte, Vertreter von Hilfsorganisationen und gegen die serbische Minderheit der Provinz Kosovo bzw. Südserbiens.
2.4.2 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. Am 10. Juni 1999 erliess der UNO-Sicherheitsrat die Resolution Nr. 1244. Darin wurde beschlossen, unter der Schirmherrschaft der Vereinten Nationen im Kosovo eine zivile Übergangsverwaltung und internationale Sicherheitskräfte einzusetzen. Auf dieser Grundlage wurde die Mission der UNO zur Interimsverwaltung im Kosovo (United Nations Interim Administration Mission in Kosovo/UNMIK) geschaffen. Zur Durchsetzung der öffentlichen Ordnung wurden zudem multinationale Streitkräfte stationiert (Kosovo Force/KFOR). Die Schweiz beteiligt sich mit einer "Swiss Company" (SWISSCOY) an der KFOR. Seit 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 (multiethnisch zusammengesetzten) lokalen Polizeikräfte (MEP/ UNMIK-Police) im Kosovo (vgl. Botschaft des Bundesrates zum Bundesbeschluss über die Schweizer Beteiligung an der multinationalen Kosovo Force vom 3. Dezember 2004 [KFOR-Botschaft], BBl 2005, 447 ff., 450).
2.4.3 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.
2.4.4 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 (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.
2.4.5 Trotz gewissen Fortschritten gilt die Lage in der "autonomen serbischen Provinz Kosovo" bzw. in Südserbien heute noch als sehr instabil. Der völkerrechtliche Status des Kosovo ist bis heute nicht geklärt (vgl. KFOR-Botschaft, BBl 2005, 450). Es kommt regelmässig 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 Mitte März 2004. Laut Berichten der UNMIK und der KFOR-Botschaft des Bundesrates hätten sich an den "interethnischen" Konflikten in Kosovo bzw. Südserbien im März 2004 zehntausende Personen beteiligt. Der Bundesrat spricht in diesem Zusammenhang von einem "schweren Rückschlag der internationalen Bemühungen zur Stabilisierung und Normalisierung der Lage in dieser Region". Es habe sich gezeigt, dass "extremistische Kreise in Kosovo fähig sind, interethnische Spannungen bewusst zu schüren und Minderheiten zu vertreiben, um ihre politischen Ziele zu verfolgen" (BBl 2005, 451).
2.4.6 In seiner 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. Seit den blutigen Zusammenstössen im März 2004 haben sich die Fronten zwischen Serben, Albanern und den Vertretern der internationalen Staatengemeinschaft laut KFOR-Botschaft des Bundesrates und Berichten der UNMIK verhärtet. Extremisten und kriminelle Gruppierungen versuchten, "das zu ihren Gunsten veränderte Umfeld für ihre Zwecke zu nutzen" (KFOR-Botschaft, BBl 2005, 450). Rund 10 Prozent aller Kosovo-Albaner, ca. 200'000 Personen, sind heute in der Schweiz wohnhaft. Nach Einschätzung des Bundesrates ist die Sicherheitslage im Kosovo "noch lange nicht stabil" (KFOR-Botschaft, BBl 2005, 452). Der Truppenbestand der KFOR beträgt heute noch über 17'000 Personen. Die KFOR arbeitet mit der lokalen multiethnischen Polizei (UNMIK-Police) eng zusammen (vgl. BBl 2005, 453, 455).
2.5 In <ref-ruling> f. E. 6 hat das Bundesgericht erwogen, dass die Abgrenzung zwischen "legitimen" Freiheitskämpfern bzw. Bürgerkriegsparteien und mutmasslichen Terroristen zu den schwierigsten Fragen des internationalen Strafrechts gehöre. Dies gelte besonders im vorliegenden Fall bzw. vor dem Hintergrund des serbisch-kosovarischen Bürgerkrieges. 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 angehört und sich dabei an Straftaten gegen serbische Sicherheitskräfte beteiligt, könne nur auf der Basis von eingehenden Sachabklärungen beurteilt werden. Im vorliegenden Fall seien 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. Im Rahmen der Rechtshilfevoraussetzung der beidseitigen Strafbarkeit müsse die Sachdarstellung des Ersuchens namentlich die Prüfung ermöglichen, ob sich die Ermittlungen wegen angeblich "terroristischer" Umtriebe gegen eine terroristische Organisation im strafrechtlichen Sinne richten. Der vorliegende Fall verlange aber auch die Ausleuchtung des politischen und völkerrechtlich-humanitären Kontextes. Weder dürfe die internationale Rechtshilfe in Strafsachen zu politischen Zwecken missbraucht werden, noch dürften Hinweise auf den angeblich politischen Charakter einer Strafverfolgung dazu führen, dass Schwerkriminelle oder Terroristen von Strafverfolgung verschont bleiben (<ref-ruling> E. 6.1 S. 345).
2.6 Im aufgehobenen Auslieferungsentscheid des BJ vom 7. April 2004 war der dem Ersuchen zugrunde liegende Sachverhalt noch wie folgt zusammengefasst worden: In den Jahren 1999-2000 bzw. ab 2002 habe der Verfolgte den "terroristischen Organisationen" OVPMB ("Befreiungsarmee für Presevo, Medvedja und Bujanovac") 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. Dem Verfolgten könne allerdings "keine direkte Tatbeteiligung" an konkreten terroristischen Straftaten zur Last gelegt werden.
2.7 In <ref-ruling> ff. E. 7 wurden dazu folgende Fragen aufgeworfen: Angeschuldigt würden von serbischer Seite primär kosovo-albanische Sicherheitskräfte Südserbiens bzw. der "autonomen Provinz" Kosovo, nämlich Angehörige der von UNO/UNMIK und OSZE/ OMIK ab Mai 2001 eingesetzten und überwachten "multiethnischen" Polizei (MEP/UNMIK-Police), die überwiegend aus ethnischen Albanern und teilweise auch aus Serben zusammengesetzt ist. Unbestrittenermassen seien vier der Mitbeschuldigten Angehörige der "multiethnischen" Polizeikräfte im Kosovo. Vor diesem Hintergrund stelle 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 (<ref-ruling> E. 7.1 S. 346). Aber auch bei der Prüfung der beidseitigen Strafbarkeit seien wesentliche Fragen offen geblieben. So sei nicht ausreichend abgeklärt worden, ob die Organisationen, die der Verfolgte angeblich unterstützte bzw. denen er angehört haben soll (1999-2000 OVPMB, ab 2002 ANA), aufgrund von verlässlichen Informationen überhaupt als "terroristisch" eingestuft werden können. Trotz entsprechenden Nachfragen des BJ hätten die serbischen Behörden keine Informationen zum Aufbau und zur Struktur der Organisationen OVPMB und ANA vorgelegt. Gemäss dem Bericht des Bundesamtes für Polizei (Dienst für Analyse und Prävention) vom 22. März 2004 habe die ANA "keine einheitliche militärisch-operative Führung". Über die Strukturen der OVPMB lägen "keine gesicherten Erkenntnisse" vor (<ref-ruling> E. 7.1 S. 347).
Ungeklärt erscheine sodann, wo sich das Haus befindet, das als Versteck gedient haben soll. Dem Verfolgten werde zwar die logistische Unterstützung der kosovo-albanischen Organisationen OVPMB und ANA vorgeworfen. Nähere Informationen dazu seien jedoch gemäss den Angaben der serbischen Behörden nicht vorhanden. Dies gelte 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 kontrastierten 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 lägen nicht vor. Ebenso wenig seien Informationen (etwa bei der UNMIK/OMIK) über die Hauptangeschuldigten eingeholt worden, bei denen es sich unbestrittenermassen um Angehörige der MEP handle (<ref-ruling> E. 7.3 S. 348).
2.8 Weiter erwog das Bundesgericht, Art. 12 Ziff. 2 lit. b EAUe bestimme, dass Zeit, Ort und Umstände der Begehung der fraglichen Delikte "so genau wie möglich" anzugeben sind. Im vorliegenden Fall wiesen die dem Verfolgten vorgeworfenen Delikte zweifelsohne einen politischen Konnex auf. Es seien daher erhöhte Anforderungen an die Ausführlichkeit, Widerspruchsfreiheit und Verlässlichkeit des Ersuchens zu verlangen. Zum einen erscheine dies erforderlich, damit die Einrede des politischen Deliktes sachgerecht beurteilt werden kann. Zum andern seien 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. Der Auslieferungsentscheid des BJ vom 7. April 2004 habe diesen Anforderungen nicht entsprochen (<ref-ruling> E. 7.4 S. 349).
Auch die Frage des Alibis bedürfe weiterer Abklärungen. Die vom Verfolgten geltend gemachten 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 sei auf Grund der bisherigen Abklärungen 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) würden im Ersuchen und dessen Ergänzungen nicht gemacht (<ref-ruling> E. 7.5 S. 349 f.). Und schliesslich sei auch die Menschenrechtslage in Serbien und Montenegro - im Hinblick auf die politische Relevanz der erhobenen Tatvorwürfe - näher abzuklären (<ref-ruling> E. 7.6 S. 350).
2.9 Am 13./14. August sowie am 17. September 2004 reichte die Botschaft von Serbien und Montenegro auf Einladung des BJ verschiedene Gesuchsergänzungen und Zusatzinformationen ein. Am 13. August und 9. September 2004 übermittelten der Dienst für Analyse und Prävention des Bundesamtes für Polizei (DAP) sowie das Eidgenössische Departement für auswärtige Angelegenheiten (EDA) dem BJ zusätzliche Amtsberichte.
2.10 Im angefochtenen Entscheid des BJ wird die Sachverhaltsdarstellung des Ersuchens und seiner diversen Ergänzungen nun wie folgt zusammengefasst:
2.10.1 Der Verfolgte habe in den Jahren 1999 und 2000 der OVPMB sowie ab 2002 der ANA angehört. In diesem Zusammenhang habe er "gegenüber den anderen Mitgliedern - mit denen er einen ständigen Telefonkontakt aufrechterhalten" habe - "vor allem eine beratende Rolle gespielt und deren Handlungen beeinflusst". Dabei habe der Verfolgte "seine Gesprächspartner zur Ausführung konkreter terroristischer Aktionen gegen Angehörige des Sicherheitsdienstes in Südserbien angestiftet und diese Aktionen vorbereitet bzw. koordiniert". Ausserdem sei er "für die Bereitstellung von Geldmitteln zur Beschaffung von Ausrüstung sowie von Waffen und Munition zuständig gewesen". Die ANA habe "am 3. Februar 2003 in Serbien einen Sicherheitsbeamten getötet". Die Täter hätten sich "danach im Haus des Verfolgten versteckt". Mitglieder der ANA hätten "am 2. März 2003 und 23. September 2003" in Serbien Sprengkörper an verschiedenen Orten angebracht, welche "in der Folge nicht explodiert" seien.
2.10.2 Gemäss Angaben der ersuchenden Behörde seien "Struktur und Aufbau" der OVPMB und der ANA "veränderlich" und "von der Anzahl der Mitglieder sowie von der politischen bzw. wirtschaftlichen Situation im betroffenen Gebiet" abhängig. In diesem Zusammenhang sei auch "die Sicherheitslage von Bedeutung". Es habe sich "gezeigt, dass sich die Struktur dieser Organisationen oft", manchmal sogar innert Wochenfrist, verändert habe. Der Verfolgte habe eine "Sondergruppe" der ANA gegründet, "welche mit der Planung und der unmittelbaren Ausführung von terroristischen Aktionen und Gewaltakten zur Beunruhigung der Einwohner beauftragt gewesen" sei. "Als eines der aktivsten Mitglieder dieser Organisation sowie als Koordinator" habe er "durch kontinuierliche und ordentliche Kontakte mit anderen Mitgliedern und durch konkrete Anweisungen deren Aktionen geleitet, Finanzhilfe aus dem Ausland, namentlich aus der Schweiz, besorgt und die Ausrüstung der Gruppe sichergestellt". In der Schweiz habe der Verfolgte "für die Organisation Geld eingezogen und dieses über eine andere Person in den Kosovo weitergeleitet". Er sei "über die Vorbereitung und Ausführung der Tötung" des serbischen Sicherheitsbeamten "informiert" gewesen. Zudem kenne er die Täter persönlich und habe mit ihnen "vor und nach der Aktion telefonisch und per SMS-Mitteilungen kommuniziert". Ausserdem hätten sich die Täter nach dem Tötungsdelikt "im Haus des Verfolgten" in Bujanovac versteckt. Eine "physische Teilnahme an der Tatausführung vor Ort" werde ihm hingegen "nicht vorgeworfen". Zudem habe der Verfolgte "die Aufstellung der Sprengladung auf einer Landstrasse im Gebiet des Dorfs Turija, welche von Angehörigen der Einheiten des serbischen Innenministeriums, der Gendarmerie und der Polizei benutzt" worden sei, "koordiniert". Er sei diesbezüglich "ausführlich durch einen Mittäter orientiert worden, ohne dabei physisch an der Tatausführung beteiligt gewesen zu sein". Schliesslich habe der Verfolgte "bei den geplanten Hinterhalten gegen die Gendarmerie im Zeitraum vom 6. bis 9. März 2003 im Gebiet der Gemeinde Bujanovac mitgewirkt, indem die Kommunikation zwischen den Mittätern über den Verfolgten, der aus der Schweiz telefoniert" habe, erfolgt sei (angefochtener Entscheid, S. 4 f. Ziff. 4.1).
2.10.3 Zwar erscheint die Sachverhaltsdarstellung des Ersuchens und seiner Ergänzungen nicht in allen Punkten konsistent. Sie entspricht jedoch insgesamt den formellen Voraussetzungen von Art. 12 Ziff. 2 lit. b des Europäischen Auslieferungsübereinkommens vom 13. Dezmeber 1957 (EAUe; SR 0.353.1).
2.11 Zu den weiteren Sachverhaltsabklärungen des BJ wird im angefochtenen Entscheid Folgendes ausgeführt:
2.11.1 Gemäss den Berichten des DAP vom 22. März und 13. August 2004 seien die OVPMB und die ANA "Nachfolgeorganisationen der UCK" und "eng miteinander verbunden". Nach Auflösung der OVPMB im Mai 2001 seien die meisten ihrer Mitglieder der ANA beigetreten. Diese sei für "Untergrundaktionen" und "Anschläge" verantwortlich, "namentlich gegen serbische Sicherheitskräfte in Südserbien". "Mit ihren gezielten Kampfhandlungen" versuche sie, "die Krisenregion zu destabilisieren und damit die internationalen Friedensbemühungen zu behindern". Die ANA habe sich "zu mehreren Anschlägen bekannt, bei denen seit 2001 ca. 25 Angehörige der Sicherheitskräfte aus Mazedonien und Serbien getötet worden" seien. Die ANA-Zellen seien "vielfach mit den lokalen kriminellen Gebietschefs verbunden". "Die Kämpfer dieser Zellen" seien "als feste Bestandteile der kriminellen Clanstrukturen in Schutzgelderpressungen, Schmuggel, Waffen-, Drogen- und Menschenhandel involviert".
2.11.2 Laut DAP hätten die US-Regierung sowie der ehemalige Chef der UNO-Verwaltung im Kosovo (UNMIK) die ANA als terroristische Organisation bezeichnet. Zwar habe die internationale Staatengemeinschaft "aufgrund von politischen Überlegungen und verschiedener Abkommen" die UCK und ihre Nachfolgeorganisationen "anfänglich grundsätzlich nicht auf Terrorlisten gesetzt". Ab Mitte 2001 sei jedoch erkannt worden, dass in den Kampfhandlungen von selbst ernannten Befreiungsbewegungen eine Gefährdung des Friedens und der Sicherheit in der Krisenregion liege. Am 17. April 2003 habe der zuständige Sonderbevollmächtigte des UNO-Generalsekretärs, Michael Steiner, eine Verwaltungsanweisung erlassen, wonach es sich bei der ANA um eine "terroristische Vereinigung" (im Sinne der UNMIK-Verfügung Nr. 2001/12 vom 14. Juni 2001) handle. Diese Verfügung sei erfolgt, nachdem sich die ANA zu einem Sprengstoffanschlag vom 12. April 2003 auf eine Eisenbahnbrücke in Zvecan bekannt habe. Am 28. Mai 2003 habe auch das Schatzamt der US-Regierung die ANA als "terroristische Organisation" bezeichnet. Zur Struktur und zum Aufbau der ANA gebe es wenig neue Erkenntnisse. Oberstes Gremium der ANA für politische Entscheidungen sei ein Exekutivorgan, welches aus elf Mitgliedern bestehe. Die Mitgliederzahl werde auf einige hundert Personen geschätzt, darunter viele frühere Mitglieder der UCK.
2.11.3 Gemäss dem Zusatzbericht des Eidgenössischen Departements für auswärtige Angelegenheiten (EDA) vom 13. August 2004 könne momentan "von einer organisierten Kraft unter dem Namen ANA" nicht mehr gesprochen werden. Im Jahre 2003 "sei das Problem jedoch noch aktuell gewesen". Vertreter der UCK hätten ausgesagt, dass die ANA "bereits vor dieser existiert habe". Die ANA habe "politische, militärische, finanzielle und eventuell auch logistische Strukturen". Selbst für die ehemaligen Vertreter der UCK sei es "nicht immer leicht", die Verästelungen innerhalb der ANA zu überblicken. "Seit dem Jahre 2004" gleiche die ANA "eher einer Gruppe von Kriminellen, als einer Organisation mit disziplinierten Kämpfern", die politische Ziele verfolgt. Ab 2004 hätten die Aktionen, die der ANA zuzurechnen sind, "mehrheitlich Erpressungen und Einschüchterungen der Bevölkerung" betroffen. Die Organisation verfüge heute über nicht mehr als 200 Mitglieder. Nur wenige davon befänden sich im Kosovo, die Mehrheit halte sich in Belgien, der Schweiz und eventuell in Italien auf. Seit dem erwähnten Attentat vom 12. April 2003 auf eine Eisenbahnbrücke in Zvecan habe sich die ANA "zu keinen weiteren Anschlägen mehr bekannt". Da die ANA die Unabhängigkeit des Kosovo von Serbien mit gewalttätigen Mitteln angestrebt habe, sei sie Mitte April 2003, nach dem Attentat von Zvecan, von der UNMIK "als terroristische Organisation eingestuft worden". Es könne nicht ausgeschlossen werden, dass seither "verschiedene Gruppierungen unter dem Deckmantel der 'ANA' gemeinrechtliche Straftaten begehen würden, ohne jeglichen politischen Hintergrund" (angefochtener Entscheid, S. 5-7. Ziff. 4.2-4.3).
2.12 Gemäss Art. 260ter Ziff. 1 StGB wird mit Zuchthaus bis zu fünf Jahren oder mit Gefängnis bestraft, wer sich an einer Organisation beteiligt, die ihren Aufbau und ihre personelle Zusammensetzung geheimhält und die den Zweck verfolgt, Gewaltverbrechen zu begehen oder sich mit verbrecherischen Mitteln zu bereichern. Ebenso macht sich strafbar, wer eine solche Organisation in ihrer verbrecherischen Tätigkeit unterstützt. 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. 3.4 S. 344; <ref-ruling> E. 4.3 S. 365 f.; <ref-ruling> E. 5c S. 574, je mit Hinweisen). Nach der Praxis des Bundesgerichtes stellen insbesondere die italienischen "Brigate Rosse", die baskische ETA und das internationale Netzwerk Al-Qaïda terroristische verbrecherische Organisation im Sinne von Art.260ter Ziff. 1 StGB dar (<ref-ruling> E. 2.2 S. 361; <ref-ruling> E.5c-d S. 574 f.; vgl. zur betreffenden teilweise nicht publizierten Rechtsprechung auch Marc Forster, Die Strafbarkeit der Unterstützung [insbesondere Finanzierung] des Terrorismus, ZStrR 121 [2003] 423 ff.).
2.12.1 Als Beteiligte im Sinne von Art. 260ter Ziff. 1 Abs. 1 StGB sind alle Personen anzusehen, welche funktionell in die kriminelle Organisation eingegliedert sind und im Hinblick auf deren verbrecherische Zweckverfolgung Aktivitäten entfalten. Diese Aktivitäten brauchen (für sich allein) nicht notwendigerweise illegal bzw. konkrete Straftaten zu sein. Es genügen namentlich auch logistische Vorkehren, die dem Organisationszweck unmittelbar dienen (wie z.B. Auskundschaften, Planen oder Bereitstellen der operativen Mittel, insbesondere Beschaffen von Fahrzeugen, Kommunikationsmitteln oder Finanzdienstleistungen usw.). Die Beteiligung setzt auch keine massgebliche Funktion innerhalb der Organisation voraus. Sie kann informeller Natur sein oder auch geheimgehalten werden (<ref-ruling> E. 2.3 S. 361 mit Hinweisen).
2.12.2 Bei Personen, die nicht in die Organisationsstruktur integriert sind, kommt die Tatvariante der Unterstützung in Frage. Diese verlangt einen bewussten Beitrag zur Förderung der verbrecherischen Aktivitäten der kriminellen Organisation. Im Gegensatz zur Gehilfenschaft zu spezifischen Straftaten (Art. 25 StGB) ist für die Unterstützung nach Art. 260ter Ziff. 1 Abs. 2 StGB der Nachweis von kausalen Tatbeiträgen im Hinblick auf ein konkretes Delikt nicht erforderlich (<ref-ruling> E. 2.4 S. 361 f. mit Hinweisen). So können namentlich das blosse Liefern von Waffen an eine terroristische oder mafiaähnliche Organisation, das Verwalten von Vermögenswerten oder andere logistische Hilfeleistungen von Aussenstehenden unter den Organisationstatbestand von Art. 260ter Ziff. 1 Abs. 2 StGB fallen. Dementsprechend besteht zwischen der Beihilfe zu konkreten Straftaten und dem Organisationstatbestand auch grundsätzlich echte Konkurrenz (BGE 128 II355 E. 2.4 S. 362 mit Hinweisen). Der subjektive Tatbestand von Art.260ter Ziff. 1 Abs. 2 StGB verlangt jedoch, dass der Unterstützende weiss oder zumindest in Kauf nimmt, dass sein Beitrag der verbrecherischen Zweckverfolgung der kriminellen Organisation dienen könnte. Blosse Sympathisanten oder "Bewunderer" von terroristischen oder mafiaähnlichen Vereinigungen fallen demgegenüber nicht unter den Organisationstatbestand (<ref-ruling> E. 2.4 S. 362 mit Hinweisen).
2.13 Gestützt auf die Zusatzberichte des DAP und des EDA muss die ANA aufgrund ihrer Struktur und ihrer verbrecherischen Aktivitäten im fraglichen Zeitraum (Frühjahr 2003) als terroristische Organisation im Sinne von Art. 260ter Ziff. 1 StGB bezeichnet werden. Bei der ANA handelte sich nach den vorliegenden Erkenntnissen um eine relativ straff geführte und paramilitärisch organisierte extremistische Untergrundorganisation mit einigen hundert aktiven Mitgliedern, die ihren Aufbau und ihre personelle Zusammensetzung geheim hielt. Ihr Ziel bestand darin, die ehemalige Bürgerkriegsregion Kosovo-Südserbien mit dem Einsatz von Gewalt politisch zu destabilisieren, um die Unabhängigkeit des Kosovo von Serbien zu erzwingen. Zu diesem Zweck verübte die ANA im Februar und März 2003 Attentate mit Schusswaffen und Sprengstoff auf serbische Sicherheitskräfte. Zumindest ab Mitte April 2003 beanspruchte sie aber auch die Urheberschaft eines Bombenanschlages gegen zivile Einrichtungen (Eisenbahnbrücke in Zvecan). Wie sich aus den Rechtshilfeakten ergibt, wurde die ANA deshalb vom zuständigen Sonderbevollmächtigten des UNO-Generalsekretärs am 17. April 2003 auf die Liste der als terroristisch eingestuften extremistischen Gruppierungen gesetzt. Dem Beschwerdeführer wird im Wesentlichen vorgeworfen, er habe der ANA (als eines ihrer aktivsten Mitglieder) angehört. Von der Schweiz aus habe er die Organisation logistisch unterstützt. Namentlich habe er sich an der Planung und Koordination von Anschlägen beteiligt und für die ANA finanzielle Mittel beschafft. Über die im Februar 2003 geplante und ausgeführte Tötung eines serbischen Polizisten sei er zumindest "informiert" gewesen. "Vor und nach der Aktion" habe er mit den Hauptverdächtigen "telefonisch und per SMS-Mitteilungen kommuniziert". Ausserdem hätten sich die Täter nach dem Tötungsdelikt in einem Haus des Beschwerdeführers versteckt. Eine "physische Teilnahme an der Tatausführung vor Ort" werde ihm hingegen "nicht vorgeworfen". Dies gelte auch für fehlgeschlagene Sprengstoffdelikte der ANA im März bzw. September 2003.
2.14 Im Falle einer strafrechtlichen Verurteilung fiele der inkriminierte Sachverhalt grundsätzlich unter Art. 260ter Ziff. 1 StGB. Damit liegt ein auslieferungsfähiges Delikt im Sinne von Art. 2 Ziff. 1 EAUe vor. Einen liquiden Alibibeweis vermag der Beschwerdeführer nicht zu erbringen. Zwar macht er geltend, er habe sich im fraglichen Zeitraum jeweils in der Schweiz aufgehalten. Die ersuchende Behörde wirft ihm jedoch keine Teilnahme an konkreten Tathandlungen in Südserbien vor; vielmehr wird er verdächtigt, die ANA von der Schweiz aus logistisch unterstützt zu haben. Auch die übrigen Einwendungen des Beschwerdeführers gegen die Sachdarstellung des Ersuchens lassen den dargelegten Verdacht nicht ohne weiteres dahinfallen. Dies gilt namentlich für sein Vorbringen, entgegen der Sachdarstellung des Ersuchens habe er nie in Bujanovac gewohnt oder dort ein Haus besessen.
Es kann offen bleiben, ob die dem Beschwerdeführer vorgeworfenen Tatbeiträge ausreichend konkret wären, um ihm darüber hinaus eine direkte strafbare Beteiligung an dem fraglichen Tötungsdelikt und an den versuchten Sprengstoffdelikten anzulasten. Welche Straftatbestände im Falle einer Anklageerhebung nach ausländischem Recht in Frage kämen, ist nicht vom schweizerischen Rechtshilferichter zu prüfen. Dass im Dispositiv des angefochtenen Entscheides der Sachverhalt, für den die Auslieferung bewilligt werden soll, im Sinne der obigen Erwägungen eingegrenzt wird, hält vor dem Bundesrecht stand. Die Begrenzung nach dem Grundsatz der Spezialität (Art. 14 Ziff. 1 EAUe) soll sicherstellen, dass der ersuchende Staat im Falle der Auslieferung lediglich Sachverhalte zur Anklage bringt, die gemäss Art. 2 Ziff. 1 EAUe auch nach schweizerischem Recht strafbar wären. Eine allfällige Ausdehnung des Anklagesachverhaltes wäre nur mit ausdrücklicher Zustimmung der schweizerischen Behörden zulässig (vgl. Art. 14 Ziff. 1 lit. a EAUe).
3. Der Beschwerdeführer hält an der Einrede fest, er werde aus politischen Gründen verfolgt. Er macht geltend, die ANA strebe als Nachfolgeorganisation der UCK ein "strategisch politisches Ziel" an. Serbien habe sich anlässlich der internationalen Friedensverhandlungen von Rambouillet im Februar 1999 geweigert, den Bürgerkrieg im Kosovo zu beenden. Bis zu jenem Zeitpunkt seien nach der Einschätzung des ICTY im Kosovo 4'000 Menschen ums Leben gekommen. Zwar sei der Bürgerkrieg nach der Intervention internationaler Truppen im Juni 1999 "offiziell" beendet worden. Die Kampfhandlungen zwischen der "albanischen Befreiungsarmee UCK" bzw. ihren Nachfolgeorganisationen und den serbischen Armee- und Polizeikräften hätten sich jedoch noch jahrelang fortgesetzt. Ende Mai 2001 hätten die "Unruhen und Kampfhandlungen" auf Vermittlung der internationalen Staatengemeinschaft "ihr Ende" gefunden. Die Nachfolgeorganisationen der UCK seien "entwaffnet" worden. Damit seien die ethnischen Konflikte in der Krisenregion zwar "eingedämmt", nicht aber gelöst worden. Serbien stehe "vor den Trümmern eines äusserst gewalttätigen, fast ein Jahrzehnt währenden Bürgerkrieges, in welchem sich die Ethnien bis hin zur massenhaften physischen Vernichtung bekämpft haben". Anfang 2003 sei "klar" geworden, "dass Unruhen oder Gewaltakte in der Krisenregion", namentlich im Presovo-Tal, "vor allem" der serbischen Seite nütze. Gewisse serbische Kreise seien weiterhin an einer Aufheizung der gespannten Lage in Südserbien bzw. an einer Radikalisierung des albanischen Widerstandes interessiert, um daraus politisch Kapital zu schlagen und die massive serbische Polizei- und Militärpräsenz zu rechtfertigen. Es bestünden sogar Anhaltspunkte dafür, dass ein Teil der dem albanischen Widerstand bzw. der ANA zugeschriebenen Gewaltakte des Jahres 2003 von serbischen Sicherheitskräften "selber inszeniert" worden sei. Am 14. Februar 2003 sei in der "Neuen Zürcher Zeitung" ein Artikel über die Hintergründe der Unruhen im Kosovo bzw. in Südserbien erschienen. Danach habe "ein Aufflammen der Gewalt" den Interessen der serbischen Seite gedient. "Albanischer Terrorismus" sei "für Belgrad ein willkommenes und im Presovo-Tal bewährtes Mittel, sich als Garant für Stabilität in der Region anzupreisen". Bei der vorliegenden Strafverfolgung stünden sich nach Ansicht des Beschwerdeführers "faktisch die ehemaligen Bürgerkriegsparteien gegenüber". Die "Widerstandskämpfer" der ANA würden aus politischen Motiven als Kriminelle oder Terroristen "stigmatisiert".
3.1 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 Art. 3 Abs. 1 IRSG).
Serbien und Montenegro sowie die Schweiz haben das Europäische Übereinkommen zur Bekämpfung des Terrorismus vom 27. Januar 1977 ratifiziert (EÜBT, SR 0.353.3). Das EÜBT ist für Serbien und Montenegro seit dem 16. August 2003 in Kraft. 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 zusammenhä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. 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. 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. 3.2 S. 342 f.; <ref-ruling> E. 4.2 S. 365; <ref-ruling> E. 9b S. 578, je mit Hinweisen).
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. 3.3 S. 343; <ref-ruling> E. 4.2 S. 365; <ref-ruling> E. 6a S. 71 f., je mit Hinweisen). 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 (<ref-ruling> E. 3.3 S. 343; <ref-ruling> E. 4 S. 363 f., je mit Hinweisen).
Der heiklen Unterscheidung zwischen "legitimen" Widerstandskämpfern bzw. Bürgerkriegsparteien und Terroristen hat der eidgenössische Gesetzgeber auch beim Erlass des neuen Art. 260quinquies StGB (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. <ref-ruling> E. 3.3 S. 343 f. mit Hinweisen). Auch die Anwendung von Art. 260ter Ziff. 1 StGB (Unterstützung bzw. Beteiligung an einer terroristischen Organisation) verlangt eine entsprechende Abgrenzung zwischen Terroristen und politischen Widerstandskämpfern. 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 (<ref-ruling> E. 3.3 S. 344 mit Hinweisen).
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. 3.4 S. 344; <ref-ruling> E. 4.3 S. 365; <ref-ruling> E. 9b S. 577 f.). Das schweizerische Strafrecht unterscheidet zwischen kriminellen Organisationen (Art. 260ter StGB), staatsgefährdenden rechtswidrigen Vereinigungen (Art. 275ter StGB) 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. 3.4 S. 344; <ref-ruling> E. 4.3 S. 365 f.; <ref-ruling> E. 5c S. 574, je mit Hinweisen).
3.5 Wie bereits dargelegt, wird dem Beschwerdeführer die Unterstützung und Beteiligung an einer terroristischen Organisation im Sinne von Art. 260ter Ziff. 1 StGB vorgeworfen, welche namentlich für ein Tötungsdelikt und für versuchte Sprengstoffanschläge im Frühjahr 2003 verantwortlich sei (vgl. oben, E. 2.13). Bei schweren Gewaltverbrechen, namentlich Tötungsdelikten, wird der politische Charakter der verfolgten Straftaten in der Regel verneint (<ref-ruling> E. 3.3 S. 343; <ref-ruling> E. 4.2 S. 365, je mit Hinweisen). Analoges muss auch für die Unterstützung von politisch motivierten terroristischen Gewalttaten gelten. Eine Ausnahme im Sinne der dargelegten Praxis (offene Bürgerkriege, moderater Widerstandkampf gegen fremde Besatzung oder diktatorische Regimes) ist im vorliegenden Fall nicht gegeben, sie wäre hier auch mit der Zielrichtung des EÜBT nur schwer zu vereinbaren. Zwar ist es im März 2004 erneut zu blutigen interethnischen Auseinandersetzungen im Kosovo gekommen. Der Bürgerkrieg ist jedoch seit mehreren Jahren formell beendet. Seither bemüht sich die internationale Staatengemeinschaft mit grossem Engagement um eine Befriedung der Krisenregion (vgl. dazu ausführlich oben, E. 2.4). Der terroristische, den Einwand des politischen Deliktes grundsätzlich ausschliessende Charakter der fraglichen Straftaten kommt im Falle der ANA namentlich dadurch zum Ausdruck, dass dieser extremistischen Organisation (jedenfalls seit Mitte April 2003) neben Attentaten auf serbische Sicherheitskräfte auch noch ein Sprengstoffanschlag gegen zivile Einrichtungen (Eisenbahnbrücke in Zvecan) vorgeworfen wird. Die Einschüchterung der Bevölkerung oder auch die Nötigung von Staaten bzw. internationalen Organisationen durch Gewaltverbrechen ist ein typisches Merkmal für terroristische Aktivitäten im Sinne des EÜBT (vgl. Ursula Cassani, Le train de mesures contre le financement du terrorisme: une loi nécessaire? SZW 75/2003 S. 293 ff., 301 f.; Forster, a.a.O., S. 444; s. auch Art. 260quinquies Abs. 1 StGB).
Nach dem Gesagten ist die Einrede des politischen Deliktes im vorliegenden Fall abzuweisen.
4. Schliesslich macht der Beschwerdeführer geltend, die menschenrechtliche Lage in Serbien verbiete eine Auslieferung. Auch das EDA habe in seinem Zusatzbericht vom 9. September 2004 "Risiken für die physische und psychische Integrität" des Beschwerdeführers festgestellt. Im Rahmen der Strafuntersuchung gegen den Verfolgten seien Mitverdächtige unbestrittenermassen körperlich misshandelt worden. Bei einer Razzia der serbischen Polizei vom 29. September 2003 sei das Haus des Beschwerdeführers in Veliki Trnovac verwüstet worden. Die vom ersuchenden Staat abgegebenen förmlichen Menschenrechtsgarantien seien ungenügend. Das EDA verweise zudem auf die Gefahr, dass die serbisch-montenegrinische Zentralbehörde sich auf eine "mangelnde Kooperation der lokal zuständigen" serbischen Justiz- und Gefängnisbehörden berufen oder diese vorschieben könnte.
4.1 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 (Art. 10 Abs. 3 BV, Art. 3 EMRK, Art. 7 und Art. 10 Ziff. 1 UNO-Pakt II [SR 0.103.2]). Niemand darf in einen Staat ausgeliefert werden, in dem ihm Folter oder eine andere Art grausamer und unmenschlicher Behandlung oder Bestrafung droht (Art. 25 Abs. 3 BV; vgl. <ref-ruling> E. 6a S. 167, 511 E. 5a S. 517, je mit Hinweisen). 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 namentlich 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).
4.2 Wie bereits in <ref-ruling>-350 E. 6-7 dargelegt wurde, handelt es sich hier um einen heiklen Fall mit politischer Färbung vor dem Hintergrund des langjährigen Bürgerkrieges in Kosovo (vgl. auch oben, E. 2.4-2.5 und 2.7). Aus den Akten ergeben sich ausserdem gewisse Bedenken bezüglich der Menschenrechtslage in Serbien, gerade im Falle eines verfolgten mutmasslichen Angehörigen einer extremistischen kosovo-albanischen Widerstandsorganisation (vgl. <ref-ruling> E. 7.6 S. 350). Allerdings vermögen diese Bedenken nicht zum Vornherein die Verweigerung jedwelcher Rechtshilfe zu rechtfertigen. Die Schweiz bewilligt gegenüber Serbien und Montenegro gestützt auf das EAUe namentlich Auslieferungen bei gemeinrechtlichen Straftaten (vgl. z.B. Urteile 1A.201/2004 vom 4. November 2004 sowie 1A.93/2002 vom 15. Mai 2002). Serbien und Montenegro sind Signatarstaaten der EMRK, des UNO-Paktes II, der UNO-Folterschutzkonvention und des EAUe. Aus den Zusatzberichten der eidgenössischen Behörden ergeben sich allmähliche Fortschritte bei der Implementierung und Durchsetzung rechtsstaatlicher Garantien in Serbien und Montenegro. Sodann handelt es sich im vorliegenden Fall um ein Strafverfahren zur Abklärung von Kapitalverbrechen (Tötungsdelikt, Bombenattentate usw.) bzw. von Delikten terroristischer Natur (vgl. oben, E. 2.13). Angesichts der Zielsetzung des EÜBT muss Rechtshilfe grundsätzlich auch für die Verfolgung politisch motivierter terroristischer Gewalttaten in Südserbien/Kosovo möglich sein.
4.3 In Anbetracht des heiklen Falles drängen sich hier jedoch besondere Vorkehren zur Gewährleistung der Grundrechte des Verfolgten auf. In problematischen Konstellationen wie der vorliegenden bestehen die schweizerischen Behörden beim ersuchenden Staat regelmässig auf förmlichen Garantieerklärungen bezüglich Einhaltung der Grund- und Menschenrechte (vgl. namentlich BGE 1A.93/2002 vom 15. Mai 2002, E. 6.2-6.4 [betreffend Auslieferung an die damalige Bundesrepublik Jugoslawien bzw. den Teilstaat Serbien]; BGE 1A.149/2004 vom 20. Juli 2004, E. 4 [betreffend Auslieferung an Albanien]; s. auch <ref-ruling> E. 6 S. 172 f. [Russland], 511 E. 6c S. 522 f. [Kasachstan]). Auch bei Auslieferungsfällen, auf die das EAUe anwendbar ist, kann sich der ersuchende Staat in einem konkreten Einzelfall zur Einhaltung bestimmter Verfahrensgarantien als Bedingung für eine Auslieferung ausdrücklich verpflichten. Dies gilt namentlich für die Zulassung unangemeldeter Haftbesuche und die Beobachtung des Strafverfahrens durch Vertreter der Botschaft des ersuchten Staates (vgl. BGE 1A.149/2004 vom 20. Juli 2004, E. 4.3; s. auch <ref-ruling> E. 6 S. 72 f., 511 E. 6c S. 522 f.).
4.4 Im vorliegenden Fall hielt das BJ fest, dass sich aufgrund der Berichte des EDA zwar "Vorbehalte bezüglich der Haftbedingungen in Serbien und Montenegro" aufdrängen. Durch die Einholung einer förmlichen Garantieerklärung seitens der ersuchenden Behörde bzw. des zuständigen Strafjustizorgans der Teilrepublik Serbien sowie angesichts der zu erwartenden "Publizität eines eventuellen Strafverfahrens gegen den Verfolgten" könne den Bedenken jedoch ausreichend Rechnung getragen werden. Dabei sei allerdings "zu verlangen, dass die Beobachtung des Strafverfahrens durch einen Vertreter der Botschaft sowie das jederzeitige Recht auf Besuch des Verfolgten während der gesamten Haft in ausdrücklichen Erklärungen der zuständigen Gerichts- bzw. Gefängnisbehörden verbrieft" wird (angefochtener Entscheid, S. 11 Ziff. 6.1). Die Einhaltung der abzugebenden Garantie sei "durch die Schweizer Botschaft in Belgrad bzw. durch eine durch sie eingesetzte Stelle" zu überwachen (angefochtener Entscheid, S. 12 Ziff. 6.3).
4.5 Wie sich aus den Rechtshilfeakten ergibt, erklärte das Ministerium für Menschen- und Minderheitsrechte von Serbien und Montenegro mit Schreiben an das BJ vom 11. August 2004, dass es sich dazu "verpflichte", dem Verfolgten die Grundrechte der EMRK und des UNO-Paktes II "zu gewähren". "Vertreter der eidgenössischen Behörden" seien zudem "berechtigt", den Verfolgten nach dessen Auslieferung "ohne jegliche Überwachungsmassnahmen zu besuchen". Der Verfolgte habe "jederzeit das Recht, sich an diese Personen zu wenden". Die Vertreter der schweizerischen Behörden seien "ermächtigt, sich über den Verfahrensstand zu erkundigen und an den Gerichtsverhandlungen teilzunehmen". Der Verfolgte werde "nicht wegen allfälliger politischer Hintergründe" der untersuchten Straftaten, "auch nicht in Form einer Erhöhung oder Verschärfung einer allfälligen Strafe, für diejenigen Delikte verfolgt oder bestraft werden, für welche die Auslieferung bewilligt wird". Mit Schreiben vom 17. September 2004 bestätigte dasselbe Ministerium, dass es "die einzige Behörde" des ersuchenden Staates sei, die gestützt auf das EAUe eine förmliche Menschenrechtsgarantie abgeben könne. Im Übrigen werde dem BJ "mitgeteilt, dass das Bezirksgericht von Vranje, vor dem das Strafverfahren" gegen den Verfolgten geführt werde, es "dem Vertreter der eidgenössischen Behörde ermöglichen" werde, "an den Gerichtsverhandlungen teilzunehmen und den Angeklagten zu besuchen".
Nach dem im Rechtshilfeverkehr zu beachtenden Grundsatz von Treu und Glauben ist davon auszugehen, dass die Behörden des ersuchenden Staates ihren förmlichen Garantieerklärungen nachkommen und dass die dafür notwendige Koordination zwischen den innerstaatlich zuständigen Behörden erfolgt. Würden sich die Behörden des ersuchendes Staates über die erwähnten Rechtshilfeauflagen hinwegsetzen, würden sie Gefahr laufen, von der Schweiz (und wahrscheinlich auch von anderen Staaten) keine Rechtshilfe mehr zu erhalten und diplomatische Konsequenzen auszulösen (vgl. BGE 1A.149/2004 vom 20. Juli 2004, E. 4.3).
4.6 Im vorliegenden Fall hat das BJ in enger Zusammenarbeit mit dem EDA sicherzustellen, dass die Haftbedingungen des Beschwerdeführers und der gegen ihn geführte Strafprozess vor Ort durch die schweizerische diplomatische Vertretung in Belgrad aufmerksam beobachtet werden und dass den oben genannten Garantieerklärungen nötigenfalls Nachachtung verschafft wird. Zu diesem Zweck müssen die schweizerischen Vertreter vereinbarungsgemäss jederzeit Zugang zum inhaftierten Verfolgten erhalten und mit diesem unbeaufsichtigt sprechen können. Ein entsprechender Hinweis ist in das Dispositiv des Auslieferungsentscheides aufzunehmen. Die fraglichen Garantieerklärungen wurden zwischen den gemäss EAUe zuständigen Behörden des ersuchenden und des ersuchten Staates für den vorliegenden Fall ausdrücklich vereinbart und halten insofern vor den gegenseitigen Verpflichtungen im Sinne des EAUe stand.
4.7 Angesichts der genannten Vorkehren sind im vorliegenden Fall keine Auslieferungshindernisse ersichtlich.
5. Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen und die Auslieferung im Sinne der obigen Erwägungen zu bewilligen ist. Entsprechend fällt eine Haftentlassung ausser Betracht; das Haftentlassungsgesuch ist abzuweisen. Die Einrede des politischen Deliktes ist nach dem Gesagten ebenfalls abzuweisen.
Der Beschwerdeführer stellt das Gesuch um unentgeltliche Rechtspflege. Da die gesetzlichen Voraussetzungen erfüllt sind und insbesondere die Bedürftigkeit des Gesuchstellers ausreichend glaubhaft gemacht erscheint, kann dem Ersuchen entsprochen werden (Art. 152 OG).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde (Verfahren 1A.4/2005), die Einrede des politischen Deliktes (Verfahren 1A.288/2004) und das Haftentlassungsgesuch werden abgewiesen.
2. Die Auslieferung des Beschwerdeführers an Serbien und Montenegro wird für den im Auslieferungsentscheid des Bundesamtes für Justiz vom 3. Dezember 2004 umschriebenen Sachverhalt bewilligt.
3. Das Dispositiv des Auslieferungsentscheides des Bundesamtes für Justiz vom 3. Dezember 2004 wird wie folgt ergänzt: Die Auslieferung wird unter Hinweis auf die erfolgten Garantieerklärungen bewilligt, wonach die Behörden des ersuchenden Staates der diplomatischen Vertretung der Schweiz die Möglichkeit einräumen, den Verfolgten jederzeit in der Haft zu besuchen, mit ihm unbeaufsichtigt zu sprechen und den gegen ihn geführten Strafprozess zu beobachten.
4. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt:
4.1 Es werden keine Kosten erhoben.
4.2 Rechtsanwalt Hansjürg Rhyner wird als unentgeltlicher Rechtsbeistand ernannt und für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse mit einem Honorar von Fr. 3'000.-- entschädigt.
5. Dieses Urteil wird dem Beschwerdeführer und dem Bundesamt für Justiz, Abteilung Internationale Rechtshilfe, Sektion Auslieferung, schriftlich mitgeteilt.
Lausanne, 28. Februar 2005
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: