Sachverhalt:
A. Der Armeeangehörige (Zeitsoldat) Oblt X._ (geb. 1974) bewarb sich um eine Stelle als Zugführer/Klassenlehrer-Gehilfe. Da er als Angehöriger der Armee auch Zugang zu militärisch als geheim klassifizierten Informationen, zu geheimem Armeematerial und zu militärischen Anlagen (Schutzzonen 2 und 3) hatte, wurde eine Personensicherheitsüberprüfung im Sinne von Art. 19 Abs. 1 lit. c des Bundesgesetzes vom 21. März 1997 über Massnahmen zur Wahrung der inneren Sicherheit (BWIS; SR 120) bzw. der Verordnung vom 19. Dezember 2001 über die Personensicherheitsprüfungen (PSPV; SR 120.4) eingeleitet. X._ stimmte dieser Überprüfung am 10. März 2003 zu.
Am 9. Juli 2003 wurde X._ von zwei Mitarbeitern der Fachstelle für Personensicherheitsprüfungen des Eidgenössischen Departementes für Verteidigung, Bevölkerungsschutz und Sport (VBS) befragt. Die Befragung wurde auf Tonträger (Minidisc) aufgenommen. Die Abklärungen ergaben, dass gegen X._ 26 bzw. 27 offene Betreibungen bzw. Verlustscheine (Forderungssumme insgesamt Fr. 67'351.60) bestanden; zudem wies er 16 Einträge wegen Verkehrsregelverletzungen auf.
Am 2. September 2003 erliess die Fachstelle Personensicherheitsprüfungen eine "Risikoverfügung mit Auflagen", mit welcher sie feststellte, X._ werde "nicht grundsätzlich als Sicherheitsrisiko im Sinne von BWIS und PSPV erachtet". Er könne jedoch als Offizier der Schweizer Armee nur mit der Auflage eingesetzt werden, dass ihm ausschliesslich (höchstens) der Zutritt zu militärischen Anlagen der Schutzzone 2 und zu vertraulich klassifizierten Informationen gestattet werde. Das Ergebnis der persönlichen Befragung wurde in der Verfügung zusammengefasst.
Am 29. September 2003 wandte sich X._ an die Rekurskommission VBS. Er beanstandete insbesondere die Art, wie die Befragung - auch die seiner Referenzen - durchgeführt worden sei, und wünschte, sich "unter fairen Bedingungen" noch einmal äussern zu können. Da die Beschwerde den Mindestanforderungen von Art. 52 Abs. 1 VwVG nicht genügte, wies sie der Präsident der Rekurskommission VBS zur Verbesserung zurück. Am 22. Oktober 2003 reichte X._ eine verbesserte Beschwerde ein.
Am 31. Januar 2004 verfügte der Präsident der Rekurskommission VBS u.a., der Schweizerischen Eidgenossenschaft, vertreten durch das Eidgenössische Departement für Verteidigung, Bevölkerungsschutz und Sport, werde eine Frist von 20 Tagen angesetzt, um ein schriftliches und von den Parteien unterzeichnetes Protokoll über die persönliche Befragung von X._ einzureichen (Ziff. 1).
B. Mit Verwaltungsgerichtsbeschwerde vom 10. Februar 2004 beantragt das Eidgenössische Departement für Verteidigung, Bevölkerungsschutz und Sport, Ziffer 1 der Präsidialverfügung der Rekurskommission VBS vom 20. Dezember 2003 aufzuheben.
Der Präsident der Rekurskommission VBS beantragt, die Beschwerde abzuweisen.
X._ hat auf eine Vernehmlassung bzw. auf ein Rechtsbegehren ausdrücklich verzichtet.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Die gestützt auf die Art. 19 des Bundesgesetzes vom 20. Dezember 1968 über das Verwaltungsverfahren (VwVG; SR 172.021) ergangene Verfügung des Präsidenten der Rekurskommission VBS unterliegt der Verwaltungsgerichtsbeschwerde ans Bundesgericht (Art. 98 lit. e OG). Eine Ausnahme im Sinne der Art. 99 bis 102 OG ist nicht gegeben.
1.2 Die angefochtene Verfügung ist ein Zwischenentscheid sowohl über die Ablehnung eines Beweisanerbietens (Ablehnung der Tonaufzeichnung der persönlichen Befragung des Beschwerdegegners als Beweismittel) als auch über eine Aktenergänzung (Anordnung einer schriftlichen Protokollierung der Befragung) im Sinne von Art. 45 Abs. 1 bzw. Abs. 2 lit. f VwVG. Solche Verfügungen sind selbständig anfechtbar, wenn sie einen nicht wieder gutzumachenden Nachteil bewirken können (Art. 97 OG i.V.m. Art. 5 und 45 Abs. 1 VwVG). Im Verfahren der Verwaltungsgerichtsbeschwerde genügt freilich ein tatsächliches Interesse für die Annahme eines schutzwürdigen Anfechtungsinteresses bzw. für die Begründung eines nicht wieder gutzumachenden Nachteils (<ref-ruling> E. 2a S. 619, mit Verweisungen). Ein solcher Nachteil liegt hier im Interesse des zur Beschwerde legitimierten Departementes (Art. 103 lit. b OG), zu wissen, ob es zur aufwendigen nachträglichen Ausfertigung eines schriftlichen Protokolls der mehrstündigen Befragung verpflichtet werden kann oder aus Gründen der Verfahrensökonomie auf eine andere Art, das Ergebnis der Befragung festzuhalten, zurückgreifen darf (vgl. <ref-ruling> E. 2d).
1.3 Auf die frist- und formgerechte Beschwerde ist daher einzutreten.
2. 2.1 Das Verfahren der Personensicherheitsprüfung ist ein Verwaltungsverfahren im Sinne von Art. 1 des Bundesgesetzes über das Verwaltungsverfahren. Die Verwaltungsbehörde stellt den Sachverhalt von Amtes wegen fest und bedient sich dabei folgender Beweismittel: Urkunden, Auskünfte der Parteien, Auskünfte oder Zeugnis von Drittpersonen, Augenschein, Gutachten von Sachverständigen (Art. 12 VwVG).
2.2 Die Vorinstanz hat erkannt, die in den Akten liegende Tonaufzeichnung der persönlichen Befragung stelle eine unzulässige Art der Protokollierung derselben dar. Das Protokoll müsse in schriftlicher Form vorliegen und von den Parteien unterzeichnet sein.
2.3 Näher geregelt wird im Verwaltungsverfahrensgesetz selber lediglich die Zeugeneinvernahme, die im Verwaltungsverfahren - im Gegensatz zum Zivilprozess - jedoch nur subsidiär zur Anwendung kommt (Art. 14 Abs. 1 VwVG; <ref-ruling> E. 2.3.3 S. 173). In diesem Fall ist ein eigentliches Einvernahmeprotokoll zu erstellen (vgl. insb. Art. 18 Abs. 2 und 3 VwVG). Dass dies grundsätzlich schriftlich zu geschehen hat, liegt auf der Hand.
Auf das Beweisverfahren der Verwaltung - welches ökonomisch durchzuführen ist (vgl. Art. 33 Abs. 2 VwVG) - finden im Übrigen gemäss Art. 19 VwVG "ergänzend" und sinngemäss die Art. 37 (Bestimmung der Beweismittel durch den Richter), 39 (Beweismassnahmen im Ausland) und 41 (Beweissicherung) sowie 43-61 (Zeugen, Urkunden, Augenschein, Sachverständige) des Bundesgesetzes vom 4. Dezember 1947 über den Bundeszivilprozess (BZP; SR 273) Anwendung.
2.4 Nicht anwendbar - auch nicht ergänzend bzw. sinngemäss - sind hingegen auf Grund dieser abschliessenden Aufzählung die entsprechenden Bestimmungen über das Parteiverhör (Art. 62 - 65 BZP; vgl. BBl 1965 II 1366) sowie die allgemeinen Grundsätze für das (gerichtliche) Verfahren (Art. 3 - 8 BZP), darunter auch jene über das Protokoll (Art. 7 BZP). Dies gilt auch im Lichte von Art. 4 VwVG, wonach Bestimmungen des Bundesrechts, die ein Verfahren eingehender regeln, Anwendung finden, soweit sie den Bestimmungen des Verwaltungsverfahrensgesetzes nicht widersprechen: Unter diesen Bestimmungen sind nicht etwa die übrigen, in Art. 19 VwVG nicht ausdrücklich erwähnten Bestimmungen des Bundeszivilprozesses zu verstehen, wie die Vorinstanz annimmt, sondern solche des Spezialverwaltungsrechts, nach welchen sich insbesondere auch die Mitwirkungspflicht der Parteien richtet (vgl. BBl 1965 II 1362/1366).
Es ist daher in einem nächsten Schritt zu prüfen, ob die im vorliegenden Fall anzuwendenden Spezialnormen (Bundesgesetz über Massnahmen zur Wahrung der inneren Sicherheit und Verordnung über die Personensicherheitsprüfungen) besondere Verfahrensbestimmungen für die Protokollierung der persönlichen Befragung enthalten.
3. Gemäss Art. 21 Abs. 5 BWIS regelt der Bundesrat die Einzelheiten der Sicherheitsprüfung, insbesondere die Einsichtsrechte der Betroffenen und der ernennenden Behörde.
3.1 Gestützt darauf hat der Bundesrat das Prüfverfahren festgelegt (Art. 8 ff. PSPV). Die Befragungen sind grundsätzlich in der Muttersprache der zu befragenden Person durchzuführen (Art. 12 Abs. 4 PSPV). Wenn die Fachstelle erwägt, eine negative Risikoverfügung oder eine solche mit Auflagen zu erlassen, gewährt sie der betroffenen Person das rechtliche Gehör, indem sie ihr Gelegenheit gibt, zum Ergebnis der Abklärungen schriftlich Stellung zu nehmen (Art. 20 Abs. 1 PSPV). Die betroffene Person kann bei der Fachstelle jederzeit Einsicht in die Prüfungsunterlagen nehmen (vgl. auch Art. 21 Abs. 2 BWIS); in der Risikoverfügung darf nur auf solche Daten abgestellt werden, die der betroffenen Person bekannt gegeben worden sind (Art. 20 Abs. 2 PSPV).
Die betroffene Person kann gemäss Art. 21 Abs. 2 BWIS und Art. 20 Abs. 3 PSPV von der Fachstelle im Weiteren verlangen, dass
a) Daten, die unrichtig oder überholt sind, berichtigt oder vernichtet werden;
b) Daten, die dem Zweck der Bearbeitung nicht entsprechen oder deren Bearbeitung aus anderen Gründen (Vermutungen oder blosse Verdächtigungen) unzulässig ist, umgehend vernichtet werden;
c) ein Bestreitungsvermerk angebracht wird.
Nähere Bestimmungen darüber, ob und in welcher Form ein Protokoll über die persönliche Befragung zu erstellen ist, lassen sich dieser Regelung nicht entnehmen.
3.2 Im Hinblick auf das Recht zur Stellungnahme und auf Bestreitung falscher Daten und Wertungen sowie schliesslich auf die Beschwerdemöglichkeit muss die Transparenz der Datenbeschaffung hingegen gewahrt werden (BBl 1994 II 1187). Es ist daher zu prüfen, inwieweit sich aus Art. 29 Abs. 2 BV bzw. aus dem Anspruch auf Gewährung des rechtlichen Gehörs, insbesondere auf Akteneinsicht, ein Anspruch auf schriftliche Protokollierung einer persönlichen Befragung ergibt.
4. 4.1 Die Wahrnehmung des Akteneinsichts- und Beweisführungsrechts durch den von einer Verfügung Betroffenen setzt eine Aktenführungspflicht der Verwaltung voraus. Die Behörden haben alles in den Akten festzuhalten, was zur Sache gehört und entscheidwesentlich sein kann (<ref-ruling> E. 3b). Dieser ursprünglich für das Strafverfahren entwickelte Grundsatz muss als Gehalt von Art. 29 Abs. 2 BV für alle Verfahrensarten gelten (Urteil 5A.20/2003 vom 22. Januar 2004, E. 2.4.1 nicht publ. in <ref-ruling>).
Auch auf Tonträger registrierte Einvernahmen bzw. Auskünfte sind oder können Beweismittel sein (vgl. Urteil 1P.704/1994 vom 27. Juni 1995 E. 2a/bb; Thomas Merkli/Arthur Aeschlimann/Ruth Herzog, Kommentar zum Gesetz vom 23. Mai 1989 über die Verwaltungsrechtspflege des Kantons Bern, Bern 1997, N 11 zu Art. 19 VRPG/BE; Reinhold Hotz, in: St. Galler Kommentar, N 30 zu Art. 29 BV) und gehören als solche in die Akten.
4.2 Das Bundesgericht hat in Bezug auf die Form von Beweisvorkehren im Verwaltungsverfahren allgemein erkannt, Auskünfte von Drittpersonen (Art. 12 lit. c VwVG) hätten gemäss dem ergänzend anwendbaren Art. 49 BZP grundsätzlich schriftlich zu erfolgen. Eine formlos eingeholte und in einer Aktennotiz festgehaltene mündliche bzw. telefonische Auskunft stelle nur insoweit ein zulässiges und taugliches Beweismittel dar, als damit bloss Nebenpunkte, namentlich Indizien oder Hilfstatsachen festgestellt würden. Seien hingegen von Drittpersonen Auskünfte zu wesentlichen Punkten des rechtserheblichen Sachverhaltes einzuholen, falle grundsätzlich nur die Form der schriftlichen Anfrage und Auskunft in Betracht. Würden Auskunftspersonen zu wichtigen tatbeständlichen Fragen dennoch mündlich befragt, sei eine Einvernahme durchzuführen und darüber ein Protokoll aufzunehmen (<ref-ruling> E. 4c; Urteil 5A.20/2003 vom 22. Januar 2004, E. 2.6 nicht publ. in <ref-ruling>).
Es entspricht denn auch einem aus dem Anspruch auf rechtliches Gehör abgeleiteten allgemeinen Verfahrensgrundsatz, dass entscheidrelevante Tatsachen und Ergebnisse schriftlich festzuhalten sind. Dazu gehört auch die Pflicht zur Protokollführung über entscheidwesentliche Abklärungen, Zeugeneinvernahmen und Verhandlungen im Rechtsmittelverfahren. Das Bundesgericht hat in einem älteren Entscheid eine allgemeine Protokollierungspflicht für das Verwaltungsverfahren noch verneint. Später hat es entschieden, dass die wesentlichen Ergebnisse eines Augenscheins in einem Protokoll oder Aktenvermerk festzuhalten oder zumindest - soweit sie für die Entscheidung erheblich sind - in den Erwägungen des Entscheids klar zum Ausdruck zu bringen seien. Wenn die Verwaltung mit einem Verfahrensbeteiligten ein Gespräch führt, ist wenigstens der wesentliche Gehalt des Gespräches im Protokoll festzuhalten (<ref-ruling> E. 4c). Im übrigen hat das Bundesgericht die Protokollierungspflicht von den konkreten Umständen des Einzelfalls abhängig gemacht (<ref-ruling> E. 3).
4.3 Für die Protokollierung einer Gerichtsverhandlung hat das Bundesgericht erkannt, der Anspruch auf rechtliches Gehör sei nur dann gewahrt, wenn das Gericht die Ausführungen und Eingaben auch tatsächlich zur Kenntnis nehme und pflichtgemäss würdige; dafür bestehe nur Gewähr, wenn die Ausführungen und Eingaben der Parteien und allfälliger Dritter (Zeugen, Sachverständige usw.) zu Protokoll genommen würden. Dies bedeute allerdings nicht, dass insbesondere sämtliche Parteiäusserungen zu protokollieren seien. Das Protokoll könne sich auf die für die Entscheidfindung im konkreten Fall wesentlichen Punkte beschränken (<ref-ruling> E. 4).
Für das Strafverfahren verlangt das Bundesgericht, dass mindestens die wesentlichen Zeugenaussagen im Protokoll schriftlich festgehalten werden. Die blosse Würdigung der Aussagen in den Erwägungen des Urteils genüge nicht; denn es könne nicht dem Richter überlassen werden, - allein und ohne Mitwirkung der Parteien - darüber zu entscheiden, welche Aussagen im Urteil erwähnt werden (<ref-ruling> E. 2a/bb).
4.4 Die strengen, für das Strafverfahren geltenden Grundsätze können zwar nicht ohne weiteres auf das Verwaltungsverfahren übertragen werden (vgl. Thomas Merkli/Arthur Aeschlimann/Ruth Herzog, a.a.O., N 9 zu Art. 19 VRPG/BE). Nach dem Gesagten ergibt sich jedoch für die persönliche Befragung einer Partei im Verwaltungsverfahren eine Protokollierungspflicht im Sinne einer Niederschrift der mündlichen Äusserungen nach ihrem wesentlichen Inhalt (vgl.Thomas Merkli/Arthur Aeschlimann/Ruth Herzog, a.a.O., N 31 zu Art. 19 VRPG). Wie weit die Protokollierungspflicht geht bzw. ob in Fällen wie hier mehr erforderlich ist, ist mit Rücksicht auf die Besonderheiten der Personensicherheitsprüfung zu beurteilen.
4.5 Sicherheitsprüfungen verlangen von den Prüfungsorganen besondere Sachkenntnisse und Einfühlungsvermögen. Ihre Durchführung ist deshalb einer spezialisierten Fachstelle übertragen (vgl. Art. 21 Abs. 1 BWIS). Die persönliche Befragung stellt einen erheblichen Eingriff in die Geheimsphäre des Betroffenen dar, da die Lebenssituation und -führung - die für die Beurteilung des Sicherheitsrisikos zentral ist - eingehend und möglichst lückenlos ausgeleuchtet werden muss. Dabei sind insbesondere enge persönliche Beziehungen, die familiäre Situation, Alkohol- oder Betäubungsmittelmissbrauch, persönliche Schulden, Nebenbeschäftigungen usw. festzustellen, was im Wesentlichen nur auf dem Weg der mündlichen Befragung zuverlässig geschehen kann (vgl. BBl 1994 II 1187).
Dass eine solche umfassende und die Intimsphäre berührende Befragung des Betroffenen, wenn sie zu einem aussagekräftigen und zuverlässigen Ergebnis führen soll, nicht in Form eines förmlichen (Partei-)Verhörs vorzunehmen ist, liegt auf der Hand. Es ist vielmehr angezeigt, die Befragung in Form eines Gespräches durchzuführen, was erlaubt, eine dem Verhalten des Befragten angepasste Atmosphäre zu schaffen. Eine solche Abklärung lässt ein wesentlich differenzierteres Bild über die Person des Befragten und dessen Verhältnisse erwarten als ein förmliches Verhör mit Wortprotokoll (vgl. auch Thomas Merkli/Arthur Aeschlimann/Ruth Herzog, a.a.O., N 17 zu Art. 19 VRPG/BE). Ein detailliertes Bild über die regelmässig vielschichtigen persönlichen Umstände ist geradezu Voraussetzung für die verlässliche Beurteilung des Sicherheitsrisikos, welche insbesondere eine Wertung im Sinne einer Prognose über das künftige persönliche Verhalten des Betroffenen umfasst. Eine förmliche Befragung, wie sie im gerichtlichen Verfahren zu erfolgen hat, erscheint dafür wenig geeignet: Der Befragte wird weniger offen und spontan antworten, wenn das Gespräch nach einem vorgegebenen Frage-Antwort-Schema geführt und nach jeder Frage bzw. Antwort unterbrochen wird, um die "Aussagen" sogleich schriftlich festzuhalten. Dadurch wird nicht nur das Gespräch in seinem Fluss gestört, sondern es verliert auch die nötige Vertraulichkeit und Dynamik. Zu beachten ist schliesslich, dass die einlässliche persönliche Befragung - soll sie zu einem zuverlässigen Ergebnis führen - bereits in Form eines Gesprächs in der Regel mehrere Stunden dauert. Ihre wörtliche Protokollierung hätte zugleich eine erhebliche Verlängerung und damit eine Mehrbelastung nicht nur der Fachstelle, sondern insbesondere auch des Betroffenen zur Folge, der die Befragung umso einschneidender empfinden muss, je länger sie dauert.
Die im Verfahren der Personensicherheitsprüfung vorzunehmende persönliche Befragung weist damit gewisse Parallelen auf zur - in Abwesenheit der Eltern und ihrer Vertreter durchgeführten - formlosen Befragung von Kindern durch die zuständige Behörde im Hinblick auf die Kinderzuteilung und das Besuchsrecht, auch wenn für diese Befragung noch wesentliche andere Gesichtspunkte massgebend sind. In solchen Fällen genügt es unter dem Gesichtswinkel des rechtlichen Gehörs, wenn das Ergebnis des Gespräches schriftlich festgehalten wird und die Parteien Gelegenheit erhalten, dazu (auch) inhaltlich Stellung zu nehmen. Der verfassungsrechtliche Anspruch auf rechtliches Gehör umfasst mit anderen Worten nicht das (schriftliche) Festhalten aller Details des geführten Gespräches (<ref-ruling> E. 4 S. 55).
Für die persönliche Befragung bei der Sicherheitsprüfung muss Ähnliches gelten: Dem Anspruch des Betroffenen auf rechtliches Gehör ist Genüge getan, wenn der wesentliche Inhalt des Gesprächs schriftlich festgehalten wird, der Befragte im Rahmen des Akteneinsichtsrechts Gelegenheit erhält, neben den Schriftstücken auch die u.a. als Beweismittel verwendbaren Tonbänder im ganzen Umfang und im Original zu hören, und er sich dazu uneingeschränkt äussern kann (vgl. Urteil 1P.704/1994 vom 27. Juni 1995 E. 2). Das rechtliche Gehör bzw. der Grundsatz der Aktenkundigkeit ist bei solchem Vorgehen nur dann verletzt, wenn lediglich die schriftliche Zusammenfassung des Gespräches und nicht auch die Original-Tonaufzeichnung desselben zu den Akten gelegt wird (vgl. Urteil des Kassationsgerichts des Kantons Zürich vom 18. November 1995, in ZR 96/1997 S. 74). Ob die persönliche Befragung auf einer so genannten Minidisc oder einem anderen gebräuchlichen Tonträger aufgezeichnet worden ist, spielt keine Rolle, wenn, wie hier, bei der Verwaltung ein für dessen Wiedergabe und Abhörung geeignetes Gerät zur Verfügung gestellt wird.
5. Die Fachstelle hat den wesentlichen Inhalt der persönlichen Befragung und das Resultat der Datenerhebung in ihrem Verfügungsentwurf vom 25. Juli 2003 zusammengefasst und dem Beschwerdegegner unter Hinweis auf die in Aussicht genommene Beurteilung zur Stellungnahme unterbreitet (vgl. Art. 21 Abs. 2 BWIS; Art. 20 Abs. 1 PSPV). Die Original-Tonaufzeichnung der persönlichen Befragung ist in die Akten eingeheftet worden. Damit muss es sein Bewenden haben. Nach dem Ausgeführten geht die Auffassung der Vorinstanz, das Festhalten der persönlichen Befragung mittels Tonträger unter Verzicht auf eine vollständige schriftliche Ausfertigung sei unzulässig, zu weit. Die Rekurskommission hat Anforderungen an die Protokollierung gestellt, für die sich keine genügende Rechtsgrundlage findet und die damit Bundesrecht verletzen. Es ist nicht erforderlich, das auf Tonträger gespeicherte Gespräch nachträglich noch in voller Länge und in seinem genauen Wortlaut in die schriftliche Form zu übertragen. Im Übrigen hat der Beschwerdegegner seinerzeit von der ihm eingeräumten Äusserungsmöglichkeit keinen Gebrauch gemacht.
Die Beschwerde ist aus diesen Gründen gutzuheissen und die angefochtene Zwischenverfügung aufzuheben.
6. Da der Beschwerdegegner keine Anträge gestellt hat, rechtfertigt es sich, ihm für das bundesgerichtliche Verfahren keine Kosten zu überbinden.

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird gutgeheissen und die Verfügung der Rekurskommission VBS (Präsident) vom 31. Januar 2004 aufgehoben.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Parteien und dem Rekurskommission VBS schriftlich mitgeteilt.
Lausanne, 13. Juli 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: