Sachverhalt:
Sachverhalt:
A. A. und B. X._ wurden im Juni 1999 mit vier Verfügungen für die Jahre 1991/92, 1993/94, 1995/96 und 1997/98 betreffend der Landes-, Gemeinde- und Kirchensteuer veranlagt. Am 10. Juli 1999 erhoben sie "Einsprache gegen die Steuerveranlagungen 1991-1998". Am 24. Mai 2000 wurden die Veranlagungen letztinstanzlich vom Verwaltungsgericht von Appenzell Ausserrhoden geschützt.
Mit Veranlagungsverfügungen und Schlussrechnungen vom jeweils 21. Juli 1999 wurden A. und B. X._ für die direkten Bundessteuern 1991/92, 1993/94 und 1997/98 veranlagt. Am 11. August 1999 reichten sie bei der Steuerverwaltung des Kantons Appenzell A.Rh. eine Eingabe ein, die sie als "Einsprache gegen die Steuerveranlagungen der Jahre 1991-98 der direkten Bundessteuern" bezeichneten und womit sie beantragten, es seien alle Berechnungen so zu korrigieren, dass der Wochenaufenthalts-Status richtig berücksichtigt werde; weiter seien alle Positionen gleich wie bei der Einsprache vom 10. Juli 1999 gegen die kantonalen Veranlagungen anzupassen. Ziff. 7 der Einsprachebegründung ist wörtlich identisch mit Ziff. 7 der Einsprache gegen die kantonalen Veranlagungen und bezieht sich auf die Hauptveranlagung 1995/96.
Nach den Akten der kantonalen Steuerverwaltung stammt die A. und B. X._ betreffende Veranlagungsverfügung und Schlussrechnung für die direkte Bundessteuer der Jahre 1995/96 vom 2. November 2000 und wurde auch erst dann zugestellt. Dazu ging nach diesem Datum bei der Steuerverwaltung keine Einsprache ein. Mit Entscheid vom 18. Dezember 2002 trat die kantonale Steuerverwaltung auf die von A. und B. X._ am 11. August 1999 erhobene Einsprache gegen die Bundessteuerveranlagungen nicht ein, soweit sich diese gegen die Veranlagung für die Jahre 1995 und 1996 richtete.
Nach den Akten der kantonalen Steuerverwaltung stammt die A. und B. X._ betreffende Veranlagungsverfügung und Schlussrechnung für die direkte Bundessteuer der Jahre 1995/96 vom 2. November 2000 und wurde auch erst dann zugestellt. Dazu ging nach diesem Datum bei der Steuerverwaltung keine Einsprache ein. Mit Entscheid vom 18. Dezember 2002 trat die kantonale Steuerverwaltung auf die von A. und B. X._ am 11. August 1999 erhobene Einsprache gegen die Bundessteuerveranlagungen nicht ein, soweit sich diese gegen die Veranlagung für die Jahre 1995 und 1996 richtete.
B. Gegen diesen Nichteintretensentscheid führten A. und B. X._ Beschwerde beim Verwaltungsgericht von Appenzell Ausserrhoden, welches die Beschwerde am 2. Juli 2003 abwies.
B. Gegen diesen Nichteintretensentscheid führten A. und B. X._ Beschwerde beim Verwaltungsgericht von Appenzell Ausserrhoden, welches die Beschwerde am 2. Juli 2003 abwies.
C. Mit Verwaltungsgerichtsbeschwerde vom 23. Februar 2004 an das Bundesgericht beantragen A. und B. X._, das Urteil des Verwaltungsgerichts vom 2. Juli 2003 sowie der Einspracheentscheid der Steuerverwaltung des Kantons Appenzell-Ausserrhoden vom 18. Dezember 2002 seien aufzuheben und es sei die Steuerverwaltung anzuweisen, auf die Einsprache vom 11. August 1999 betreffend Steuerveranlagung 1995/96 zur direkten Bundessteuer einzutreten.
Die Steuerverwaltung und das Verwaltungsgericht des Kantons Appenzell-Ausserrhoden sowie die Eidgenössische Steuerverwaltung, Hauptabteilung Direkte Bundessteuer, Verrechnungssteuer, Stempelabgaben, schliessen auf Abweisung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. 1.1 Der angefochtene Entscheid des Verwaltungsgerichts des Kantons Appenzell-Ausserrhoden ist ein auf Steuerrecht des Bundes gestütztes, letztinstanzliches kantonales Urteil, das mit Verwaltungsgerichtsbeschwerde beim Bundesgericht angefochten werden kann (Art. 97 Abs. 1 OG in Verbindung mit <ref-law> und Art. 98 lit. g OG sowie Art. 146 des Bundesgesetzes vom 14. Dezember 1990 über die direkte Bundessteuer [DBG; SR 621.11]). Die Beschwerdeführer sind durch den angefochtenen Entscheid beschwert und nach Art. 103 lit. a OG zur Beschwerdeführung legitimiert. Auf ihre form- und fristgerecht eingereichte Beschwerde ist einzutreten.
1.2 Im Verfahren der Verwaltungsgerichtsbeschwerde bildet einzig der letztinstanzliche kantonale Entscheid Prozessgegenstand (vgl. Art. 98 lit. g OG). Auf die vorliegende Beschwerde kann daher nicht eingetreten werden, soweit die Beschwerdeführer den Einspracheentscheid der Steuerverwaltung mitanfechten (<ref-ruling> E. 1e S. 44 f.; nicht publizierte E. 1.1 zu <ref-ruling>).
1.3 Mit der Verwaltungsgerichtsbeschwerde können die Verletzung von Bundesrecht einschliesslich Überschreitung oder Missbrauch des Ermessens (Art. 104 lit. a OG) gerügt werden. Hat - wie hier - als Vorinstanz eine richterliche Behörde entschieden, so ist das Bundesgericht an deren Sachverhaltsfeststellung gebunden, wenn der Sachverhalt nicht offensichtlich unrichtig oder unvollständig oder unter Verletzung wesentlicher Verfahrensvorschriften ermittelt worden ist (Art. 105 Abs. 2 OG).
1.3 Mit der Verwaltungsgerichtsbeschwerde können die Verletzung von Bundesrecht einschliesslich Überschreitung oder Missbrauch des Ermessens (Art. 104 lit. a OG) gerügt werden. Hat - wie hier - als Vorinstanz eine richterliche Behörde entschieden, so ist das Bundesgericht an deren Sachverhaltsfeststellung gebunden, wenn der Sachverhalt nicht offensichtlich unrichtig oder unvollständig oder unter Verletzung wesentlicher Verfahrensvorschriften ermittelt worden ist (Art. 105 Abs. 2 OG).
2. 2.1 Veranlagungsverfügungen betreffend die direkte Bundessteuer haben eine Rechtsmittelbelehrung zu enthalten und sind dem Steuerpflichtigen schriftlich zu eröffnen (<ref-law>). Die Form der Zustellung wird vom Gesetz nicht vorgeschrieben (Martin Zweifel, in: Zweifel/Athanas [Hrsg.], Kommentar zum Schweizerischen Steuerrecht, Bd. I/2b, Basel/Genf/München 2000, N 18 zu <ref-law>). Anders als die Einsprache- und Beschwerdeentscheide werden die Veranlagungen als so genannte Massenverfügungen regelmässig bloss mit einfacher Briefpost versandt, was allerdings den Zustellungsnachweis erschwert (Urteil des Bundesgerichts 2A.495/1999 vom 21. März 2000, E. 2b). Gegen die Veranlagungsverfügung kann der Steuerpflichtige innert 30 Tagen nach der (postalischen) Zustellung bei der Veranlagungsbehörde schriftlich Einsprache erheben (<ref-law>). Die Frist beginnt mit dem auf die Eröffnung folgenden Tage. Sie gilt als eingehalten, wenn die Einsprache am letzten Tag der Frist bei der Veranlagungsbehörde eingelangt ist, der schweizerischen Post oder einer schweizerischen diplomatischen oder konsularischen Vertretung im Ausland übergeben wurde (Art. 133 Abs. 1 OG). Auf verspätete Einsprachen wird nur eingetreten, wenn der Steuerpflichtige nachweist, dass er durch Militär- oder Zivildienst, Krankheit, Landesabwesenheit oder andere erhebliche Gründe an der rechtzeitigen Einreichung verhindert war und dass die Einsprache innert 30 Tagen nach Wegfall der Hinderungsgründe eingereicht wurde (<ref-law>).
2.2 Zu den Gültigkeitsvoraussetzungen einer Einsprache gehört das Vorliegen eines Anfechtungsobjekts, d.h. einer (definitiven) Veranlagung. Die Einsprache gegen ein unzulässiges Anfechtungsobjekt ist nicht korrigierbar. Dazu zählt etwa die Einsprache gegen eine provisorische Veranlagung (Zweifel, a.a.O., N 25 zu <ref-law>). Fehlt es überhaupt an einer Verfügung, liegt ebenfalls kein Anfechtungsobjekt vor, gegen das ein Rechtsmittel erhoben werden könnte. Es ist daher ausgeschlossen, gegen eine zukünftige Veranlagung vorsorglich Einsprache zu erheben.
2.3 Es ist unbestritten und im Übrigen von der Vorinstanz für das Bundesgericht verbindlich festgestellt, dass den Beschwerdeführern die Bundessteuerveranlagungen 1995/96 spätestens mit der bei den Akten liegenden Veranlagungen vom 2. November 2000 zugestellt worden sind und dagegen bei der Steuerverwaltung innert der nachfolgenden Frist von 30 Tagen keine Einspracheschrift eingegangen ist. Umstritten ist, ob den Beschwerdeführern bereits früher, nämlich am 21. Juli 1999 zusammen mit den definitiven Veranlagungen für die direkten Bundessteuern 1991/92, 1993/94 und 1997/98 auch eine solche für die Jahre 1995/96 zugegangen ist.
2.4 In der Regel obliegt der Nachweis der Eröffnung einer Veranlagungsverfügung der Steuerbehörde (vgl. <ref-ruling> E. 3b S. 100; Urteile des Bundesgerichts 2A.495/1999 vom 31. März 2000, E. 2b und 4b, sowie 2A.70/1997 vom 4. März 1998, E. 2). Dies leitet sich aus dem Grundsatz ab, dass die Beweislast für eine Parteihandlung jene Partei trifft, welche diese Handlung vorzunehmen hat und daraus Rechte ableitet (vgl. <ref-law>). Umgekehrt gilt der Grundsatz auch für den Steuerpflichtigen, wenn er aus einer Tatsache Rechte zu seinen Gunsten geltend macht. Ausnahmsweise tritt eine Umkehr der Beweislast ein, wenn eine Partei den Beweis aus Gründen nicht erbringen kann, die nicht von ihr, sondern von der Gegenpartei zu verantworten sind (<ref-ruling> E. 3 S. 257 f.; Urteil des Bundesgerichts 2A.70/1997 vom 4. März 1998, E. 2a).
2.5 Nach Angaben der Steuerverwaltung erging die definitive Veranlagung der Beschwerdeführer für die direkte Bundessteuer der Jahre 1995/96 erst am 2. November 2000. Dass eine solche diesen in der Folge zugestellt wurde, ist unbestritten. Die Beschwerdeführer behaupten jedoch, bereits mit Verfügung vom 21. Juli 1999 gleichzeitig mit den Verfügungen für die Jahre 1991/92, 1993/94 und 1997/98 auch für die Jahre 1995/96 veranlagt worden zu sein. Da die Beschwerdeführer aus dieser behaupteten früheren Veranlagung Rechte ableiten, tragen sie dafür die Beweislast. Sie wenden dagegen freilich ein, sie könnten den entsprechenden Nachweis nicht erbringen, weil sie die fragliche Verfügung ihrer Einsprache bei der Steuerverwaltung beigelegt hätten. Diese habe zu verantworten, dass die Verfügung unauffindbar sei und dementsprechend die Beweislast zu tragen.
2.6 Die Vorinstanz hat festgestellt, die Beschwerdeführer hätten keinen Beweis dafür erbracht, das behauptete Anfechtungsobjekt vom 21. Juli 1999 der Steuerverwaltung zugestellt zu haben. Das bei den Akten liegende Einsprache-Original vom 11. August 1999 weise denn auch auf keinerlei mitgesandte Beilagen hin, wozu die Beschwerdeführer damals als Einsprecher auch nicht verpflichtet gewesen seien. Unter diesen Umständen sei davon auszugehen, dass die Beschwerdeführer die angebliche Veranlagung vom 21. Juli 1999 der Steuerverwaltung nie zurückgeschickt hätten, weshalb diese für das Fehlen eines entsprechenden Beweises auch nicht einzustehen habe. Mit Blick auf Art. 105 Abs. 2 OG sind die diesbezüglichen tatsächlichen Feststellungen der Vorinstanz nicht zu beanstanden, womit auch deren Folgerung, die Beschwerdeführer trügen die Beweislast für den Eingang der behaupteten Veranlagung im Juli/August 1999, nicht gegen Bundesrecht verstösst.
Auch wenn es sodann ungewöhnlich erscheinen mag, dass die Steuerverwaltung die Veranlagungen für die kantonalen Steuern der Jahre 1991-1998 sowie der direkten Bundessteuern der Jahre 1991-1994 und 1997/98 praktisch gleichzeitig eröffnete und lediglich die Jahre 1995/96 davon ausnahm, so ist das doch nicht auszuschliessen. Dafür mag es verschiedene Gründe wie entsprechende Unklarheiten bis hin zu einem eventuellen Versehen geben, worauf es aber nicht ankommt. Entscheidend ist vielmehr, dass sich die fragliche Veranlagung weder in den Akten befindet noch die Beschwerdeführer eine solche vorlegen können. Vom Beschwerdeführer als Treuhänder dürfte im Übrigen erwartet werden, er hätte sich jedenfalls eine Kopie der Veranlagung angefertigt und in auffindbarer Weise bei sich abgelegt, hätte er eine solche erhalten und das Original als Beilage zur Einsprache vom 11. August 1999 wieder zurückgeschickt. Dass sich die Beschwerdeführer in ihrer Einspracheschrift auch zu den Jahren 1995/96 geäussert haben, lässt sich damit erklären, dass die Veranlagungen für die kantonalen Steuern und die direkte Bundessteuer auf den gleichen Grundlagen beruhen und die Einsprachebegründung in beiden Zusammenhängen identisch war. Um den entsprechenden Text zu erstellen, musste den Beschwerdeführern daher keine separate Veranlagung für die direkte Bundessteuer vorliegen. Gemäss den Akten der Steuerverwaltung gibt es sodann keine andere Veranlagungsverfügung für die Jahre 1995/96 als diejenige vom 2. November 2000 und beziehen sich die Veranlagungsprotokolle, welche das Datum des 12. Juli 1999 tragen, einzig auf die Jahre 1991-1994 sowie 1997/98. Unter diesen Umständen ist auch die Feststellung der Vorinstanz, die Beschwerdeführer seien für die Jahre 1995/96 erst am 2. November 2000 veranlagt worden, mit Blick auf Art. 105 Abs. 2 OG nicht zu beanstanden.
Im Übrigen scheinen sich die Beschwerdeführer ursprünglich gar nicht am Verfügungsdatum vom 2. November 2000 gestossen zu haben. Noch in ihrer Argumentation vor der Steuerverwaltung gingen sie in einem Schreiben vom 10. Juni 2002 selber davon aus, erst dann für die direkte Bundessteuer der Jahre 1995/96 veranlagt worden zu sein. Erst nachdem in der Folge die Steuerverwaltung ihre Einsprache als verfrüht erkannt hatte und darauf nicht eingetreten war, änderten die Beschwerdeführer ihren Standpunkt und machten nunmehr geltend, bereits früher, d.h. im Juli/August 1999 eine Veranlagungsverfügung erhalten zu haben. Auch dieser Wechsel in der Argumentation der Beschwerdeführer unterstreicht, dass die tatsächlichen Feststellungen der Vorinstanz nicht offensichtlich unrichtig sind.
2.7 Die Einsprache der Beschwerdeführer erweist sich demnach als verfrüht. Damit ist davon auszugehen, dass sie gegen die definitive Veranlagung bei der direkten Bundessteuer für die Jahre 1995/96 nicht rechtzeitig Einsprache erhoben haben. Auch die späteren Rechtsschriften der Beschwerdeführer vermögen diesen Mangel nicht zu beheben, ist doch kein Grund für die ausnahmsweise Zulässigkeit einer verspätet erhobenen Einsprache gemäss <ref-law> ersichtlich.
2.7 Die Einsprache der Beschwerdeführer erweist sich demnach als verfrüht. Damit ist davon auszugehen, dass sie gegen die definitive Veranlagung bei der direkten Bundessteuer für die Jahre 1995/96 nicht rechtzeitig Einsprache erhoben haben. Auch die späteren Rechtsschriften der Beschwerdeführer vermögen diesen Mangel nicht zu beheben, ist doch kein Grund für die ausnahmsweise Zulässigkeit einer verspätet erhobenen Einsprache gemäss <ref-law> ersichtlich.
3. 3.1 Die Beschwerdeführer berufen sich schliesslich auf den Grundsatz von Treu und Glauben und auf die so genannte "kunden- resp. bürgerfreundliche Verwaltungsführung". Danach habe die Steuerverwaltung ihre Einsprache vom 11. August 1999 kommentarlos entgegengenommen und die Beschwerdeführer spätestens mit der Verfügung vom 2. November 2000 darauf aufmerksam machen müssen, dass gegen die nachträglich ergangene Verfügung über die streitige Periode, zu der bereits verfrüht Einsprache erhoben worden war, nochmals innert Frist Einsprache eingereicht werden müsse.
3.2 Die Beschwerdeführer legen nicht dar und es ist auch nicht ersichtlich, inwieweit sie aus dem Prinzip einer kunden- bzw. bürgerfreundlichen Verwaltungsführung Rechte ableiten könnten, die ihnen im vorliegenden Zusammenhang zugute kämen. Aber auch der Grundsatz von Treu und Glauben (vgl. Art. 5 Abs. 3 und Art. 9 BV) erweist sich nicht als verletzt. Die Steuerverwaltung ist nicht gehalten, bei der Zustellung einer Veranlagung in den Akten nachzuforschen, ob eventuell bereits vorgängig eine (verfrühte) Einsprache eingegangen ist, um dann den Steuerpflichtigen ausdrücklich darauf aufmerksam zu machen, er müsse nochmals eine solche einreichen. Der Steuerpflichtige wird dadurch denn auch überhaupt nicht in seinen Rechten gekürzt; vielmehr bleibt sein Einspracherecht unangetastet, und die Pflicht der Steuerbehörde, die Veranlagungsverfügung mit einer Rechtsmittelbelehrung zu versehen (<ref-law>), führt dazu, dass er auf die Einsprachemöglichkeit und die entsprechende Frist ausdrücklich hingewiesen wird. Dies ist im vorliegenden Fall denn auch geschehen. Dass eine besondere vertrauensbegründende Ausgangslage gegeben wäre, die einen Grund für eine darüber hinaus gehende Anwendung des Vertrauensprinzips setzen würde, ist nicht ersichtlich. Namentlich können die Beschwerdeführer aus der Entgegennahme ihrer Einsprache vom 11. August 1999 nichts zu ihren Gunsten ableiten, musste die Steuerverwaltung diese doch insoweit in Empfang nehmen, als sie sich in gültiger Weise gegen die Veranlagungen der anderen fraglichen Jahre richtete. Die Steuerverwaltung war damals nicht gehalten, bereits eine Vorprüfung vorzunehmen und die Beschwerdeführer darauf aufmerksam zu machen, für die Jahre 1995/96 liege noch gar kein Anfechtungsobjekt vor. Sie hat somit nicht gegen den Grundsatz von Treu und Glauben verstossen.
3.2 Die Beschwerdeführer legen nicht dar und es ist auch nicht ersichtlich, inwieweit sie aus dem Prinzip einer kunden- bzw. bürgerfreundlichen Verwaltungsführung Rechte ableiten könnten, die ihnen im vorliegenden Zusammenhang zugute kämen. Aber auch der Grundsatz von Treu und Glauben (vgl. Art. 5 Abs. 3 und Art. 9 BV) erweist sich nicht als verletzt. Die Steuerverwaltung ist nicht gehalten, bei der Zustellung einer Veranlagung in den Akten nachzuforschen, ob eventuell bereits vorgängig eine (verfrühte) Einsprache eingegangen ist, um dann den Steuerpflichtigen ausdrücklich darauf aufmerksam zu machen, er müsse nochmals eine solche einreichen. Der Steuerpflichtige wird dadurch denn auch überhaupt nicht in seinen Rechten gekürzt; vielmehr bleibt sein Einspracherecht unangetastet, und die Pflicht der Steuerbehörde, die Veranlagungsverfügung mit einer Rechtsmittelbelehrung zu versehen (<ref-law>), führt dazu, dass er auf die Einsprachemöglichkeit und die entsprechende Frist ausdrücklich hingewiesen wird. Dies ist im vorliegenden Fall denn auch geschehen. Dass eine besondere vertrauensbegründende Ausgangslage gegeben wäre, die einen Grund für eine darüber hinaus gehende Anwendung des Vertrauensprinzips setzen würde, ist nicht ersichtlich. Namentlich können die Beschwerdeführer aus der Entgegennahme ihrer Einsprache vom 11. August 1999 nichts zu ihren Gunsten ableiten, musste die Steuerverwaltung diese doch insoweit in Empfang nehmen, als sie sich in gültiger Weise gegen die Veranlagungen der anderen fraglichen Jahre richtete. Die Steuerverwaltung war damals nicht gehalten, bereits eine Vorprüfung vorzunehmen und die Beschwerdeführer darauf aufmerksam zu machen, für die Jahre 1995/96 liege noch gar kein Anfechtungsobjekt vor. Sie hat somit nicht gegen den Grundsatz von Treu und Glauben verstossen.
4. Die Verwaltungsgerichtsbeschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang werden die Beschwerdeführer unter Solidarhaft kostenpflichtig (Art. 156 Abs. 1 und 7, Art. 153 und 153a OG).

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird den Beschwerdeführern unter Solidarhaft auferlegt.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird den Beschwerdeführern unter Solidarhaft auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, der Steuerverwaltung des Kantons Appenzell Ausserrhoden und dem Verwaltungsgericht von Appenzell Ausserrhoden sowie der Eidgenössischen Steuerverwaltung schriftlich mitgeteilt.
Lausanne, 7. Oktober 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: