Sachverhalt: Sachverhalt: A. Der X._ (nachfolgend: Verband) bezweckt gemäss seinen Vereinsstatuten (nach Art. 60 ff. ZGB), die gemeinsamen Interessen der Mitglieder zu wahren. Im Vordergrund stehen die allgemeine Interessenwahrung für diesen Berufsverband, die Förderung der technischen Entwicklung im Tätigkeitsbereich der Mitglieder sowie der Berufs- und Weiterbildung, die Behandlung von Themen des Umweltschutzes und der Arbeitssicherheit, die Zusammenarbeit mit Behörden und Verbänden im In- und Ausland sowie die Pflege der persönlichen Beziehungen und Zusammenarbeit. Der Verband liess sich 1995 im Register für Mehrwertsteuerpflichtige eintragen und bezeichnete bei der Anmeldung seine Geschäftstätigkeit als "Erbringung von Dienstleistungen". Im Februar 1999 prüfte die Eidgenössische Steuerverwaltung, Hauptabteilung Mehrwertsteuer (nachfolgend: Verwaltung), bei einer Kontrolle in dessen Betrieb die Steuerperioden des 1. Quartals 1995 bis zum 3. Quartal 1998, das heisst den Zeitraum vom 1. Januar 1995 bis zum 30. September 1998. Sie stellte fest, bei den vom Verband erhobenen Mitgliederbeiträgen handle es sich um von der Steuer ausgenommene Umsätze (im Sinne von Art. 14 Ziff. 11 der Verordnung vom 22. Juni 1994 über die Mehrwertsteuer [MWSTV; AS 1994 S. 1464 und nachfolgende Änderungen]), für welche die Steuerpflicht nicht gegeben sei. Deshalb korrigierte die Verwaltung die geltend gemachten Vorsteuern mit der Ergänzungsabrechnung Nr. 110'111 vom 12. Februar 1999 und stellte insgesamt eine Steuer von Fr. 63'687.-- in Rechnung. Gleichzeitig ordnete sie die Löschung des Verbands aus dem Register der Mehrwertsteuerpflichtigen an, weil die Voraussetzungen gemäss Art. 17 MWSTV nicht erfüllt waren und eine freiwillige Optierung für die Steuerpflicht nicht in Frage kam. Der Verband liess sich 1995 im Register für Mehrwertsteuerpflichtige eintragen und bezeichnete bei der Anmeldung seine Geschäftstätigkeit als "Erbringung von Dienstleistungen". Im Februar 1999 prüfte die Eidgenössische Steuerverwaltung, Hauptabteilung Mehrwertsteuer (nachfolgend: Verwaltung), bei einer Kontrolle in dessen Betrieb die Steuerperioden des 1. Quartals 1995 bis zum 3. Quartal 1998, das heisst den Zeitraum vom 1. Januar 1995 bis zum 30. September 1998. Sie stellte fest, bei den vom Verband erhobenen Mitgliederbeiträgen handle es sich um von der Steuer ausgenommene Umsätze (im Sinne von Art. 14 Ziff. 11 der Verordnung vom 22. Juni 1994 über die Mehrwertsteuer [MWSTV; AS 1994 S. 1464 und nachfolgende Änderungen]), für welche die Steuerpflicht nicht gegeben sei. Deshalb korrigierte die Verwaltung die geltend gemachten Vorsteuern mit der Ergänzungsabrechnung Nr. 110'111 vom 12. Februar 1999 und stellte insgesamt eine Steuer von Fr. 63'687.-- in Rechnung. Gleichzeitig ordnete sie die Löschung des Verbands aus dem Register der Mehrwertsteuerpflichtigen an, weil die Voraussetzungen gemäss Art. 17 MWSTV nicht erfüllt waren und eine freiwillige Optierung für die Steuerpflicht nicht in Frage kam. B. Die Verwaltung bestätigte mit Entscheid vom 3. April 2001 die Löschung mangels Steuerpflicht und die Nachbelastung von Fr. 63'687.--. Die hiergegen erhobene Einsprache wies sie am 16. Januar 2003 ab, soweit sie darauf eintrat. Gegen diesen Einspracheentscheid wandte sich der Verband am 17. Februar 2003 an die Eidgenössische Steuerrekurskommission (nachfolgend: Rekurskommission); diese hiess am 28. Januar 2004 die Beschwerde teilweise gut, wies die Sache zur Berechnung der Mehrwertsteuer abzüglich Vorsteuer an die Verwaltung zurück (Dispositiv Ziff. 1) und stellte fest, der Verband sei zu Recht nicht als mehrwertsteuerpflichtig erklärt worden. Die abgelieferte Steuer sei ihm zurückzuerstatten. Im Übrigen habe die Verwaltung den Verband, dem reduzierte Verfahrenskosten auferlegt wurden (Dispositiv Ziff. 3), zu entschädigen (Dispositiv Ziff. 6). B. Die Verwaltung bestätigte mit Entscheid vom 3. April 2001 die Löschung mangels Steuerpflicht und die Nachbelastung von Fr. 63'687.--. Die hiergegen erhobene Einsprache wies sie am 16. Januar 2003 ab, soweit sie darauf eintrat. Gegen diesen Einspracheentscheid wandte sich der Verband am 17. Februar 2003 an die Eidgenössische Steuerrekurskommission (nachfolgend: Rekurskommission); diese hiess am 28. Januar 2004 die Beschwerde teilweise gut, wies die Sache zur Berechnung der Mehrwertsteuer abzüglich Vorsteuer an die Verwaltung zurück (Dispositiv Ziff. 1) und stellte fest, der Verband sei zu Recht nicht als mehrwertsteuerpflichtig erklärt worden. Die abgelieferte Steuer sei ihm zurückzuerstatten. Im Übrigen habe die Verwaltung den Verband, dem reduzierte Verfahrenskosten auferlegt wurden (Dispositiv Ziff. 3), zu entschädigen (Dispositiv Ziff. 6). C. Gegen den Entscheid der Rekurskommission hat die Verwaltung am 1. März 2004 Verwaltungsgerichtsbeschwerde an das Bundesgericht geführt. Sie beantragt, dieses Urteil bezüglich der Ziffern 1, 3 und 6 des Dispositivs aufzuheben und den Einspracheentscheid vom 16. Januar 2003 bis auf die Kostenregelung zu bestätigen. Der Verband (Beschwerdegegner) beantragt, die Beschwerde abzuweisen, den Einspracheentscheid der Verwaltung aufzuheben und den Entscheid der Rekurskommission eventuell zu bestätigen. Die Rekurskommission hat auf eine Stellungnahme verzichtet. 