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. 