Sachverhalt:
A. In der gegen die Torocom AG laufenden Betreibung Nr. 149325 des Betreibungsamtes Zürich 9 verlangte die Schweizerische Eidgenossenschaft, Eidg. Steuerverwaltung, Hauptabteilung Mehrwertsteuer (nachfolgend EStV), mit Gesuch vom 19. Februar 2007, gestützt auf ihren mit Rechtskraftbescheinigung versehenen Einspracheentscheid vom 7. März 2005 sei für den Betrag von Fr. 38'883.-- definitive Rechtsöffnung zu erteilen.
Mit Verfügung vom 20. März 2007 trat das Bezirksgericht Zürich auf das Rechtsöffnungsgesuch nicht ein. Die hiergegen erhobene Nichtigkeitsbeschwerde hat das Obergericht des Kantons Zürich abgewiesen, soweit darauf einzutreten war.
B. Gegen diesen Rechtsöffnungsentscheid erhob die EStV sowohl Beschwerde in Zivilsachen ans Bundesgericht (Nr. 5A_264/2007) als auch Nichtigkeitsbeschwerde an das Obergericht des Kantons Zürich. Mit Entscheid vom 14. August 2007 wies dieses die Nichtigkeitsbeschwerde ab. Dagegen hat die EStV eine weitere Beschwerde in Zivilsachen erhoben (Nr. 5A_495/2007). In der Sache selbst wurden keine Vernehmlassungen eingeholt.

Das Bundesgericht zieht in Erwägung:
1. Verfahrensparteien, Sachverhalt und Rechtsfragen in den Verfahren Nrn. 5A_264/2007 und 5A_495/2007 sind identisch. Überdies sind die Verfahren insofern verknüpft, als es prozessual um die Frage geht, gegen welchen Entscheid innerhalb des kantonalen Instanzenzuges Beschwerde in Zivilsachen erhoben werden kann bzw. muss. Die beiden Verfahren sind daher in sinngemässer Anwendung von Art. 24 BZP i.V.m. Art. 71 BGG zu vereinigen (vgl. <ref-ruling> E. 1 S. 394; <ref-ruling> E. 1 S. 271 f.).
In einem jüngsten Leitentscheid zum Verhältnis zwischen den zürcherischen Rechtsöffnungsinstanzen und der Beschwerde in Zivilsachen hat das Bundesgericht festgehalten (zur Publ. bestimmtes Urteil 5A_42/2007, E. 2), dass das Obergericht des Kantons Zürich unbekümmert um den nicht mit dem neuen BGG harmonisierten § 285 ZPO/ZH in allen Fällen auf Nichtigkeitsbeschwerden gegen erstinstanzliche Rechtsöffungsentscheide eintrete und dabei als oberes kantonales Gericht im Sinn von Art. 75 Abs. 2 BGG fungiere. Weil die Beschwerde in Zivilsachen nur gegen Entscheide letzter kantonaler Instanzen zulässig sei (Art. 75 Abs. 1 BGG) könne deshalb auf direkt gegen erstinstanzliche Rechtsöffnungsentscheide des Kantons Zürich eingereichte Beschwerden mangels Ausschöpfung des kantonalen Instanzenzuges nicht eingetreten werden. Jedoch müsse der erstinstanzliche Entscheid mit Bezug auf Rügen, welche das Obergericht nicht oder mit engerer Kognition als das Bundesgericht geprüft habe, mitangefochten werden (sog. Dorénaz-Praxis).
Das Bundesgericht hat damit die unsichere Rechtslage geklärt, die sich aus dem auf das frühere OG zugeschnittenen, noch nicht auf das BGG abgestimmten § 285 ZPO/ZH ergab. Freilich können die genannten Grundsätze wegen des Gebotes von Treu und Glauben erst ab der erfolgten Publikation des Urteils 5A_42/2007 gelten und darf es der EStV nicht zum Schaden gereichen, dass sie den erstinstanzlichen Rechtsöffnungsentscheid nicht in der gegen den oberinstanzlichen Entscheid gerichteten Beschwerde mitangefochten, sondern diesen direkt mit eigener Beschwerde angefochten hat.
Im Übrigen sind Rechtsöffnungsentscheide Endentscheide im Sinn von Art. 90 BGG und unterliegen grundsätzlich der Beschwerde in Zivilsachen (Art. 72 Abs. 2 lit. a BGG). Sodann stellen sie keine vorsorglichen Massnahmen im Sinn von Art. 98 BGG dar, weshalb alle Rügen gemäss Art. 95 und 96 BGG zulässig sind (<ref-ruling> E. 1.5 S. 400). Der notwendige Streitwert von Fr. 30'000.-- ist erreicht (Art. 74 Abs. 2 lit. b BGG).
Auf die Beschwerden ist nach dem Gesagten einzutreten und sie sind materiell zu behandeln. Insbesondere kann die Frage, ob ein vollstreckbarer definitiver Rechtsöffnungstitel im Sinn von Art. 80 Abs. 1 SchKG vorliegt, als reine Rechtsfrage mit voller Kognition beurteilt werden (Art. 106 Abs. 1 BGG).
2. Nach den Erwägungen im erstinstanzlichen Rechtsöffnungsentscheid gab die EStV für ihren als Rechtsöffnungstitel ins Recht gelegten Steuerentscheid keinen Zustellnachweis zu den Akten. Mit der blossen Rechtskraftbescheinigung sei dessen Vollstreckbarkeit nicht genügend nachgewiesen, wenn der Schuldner den Erhalt bestreite. Vielmehr habe die Behörde den urkundlichen Beweis für die Zustellung zu erbringen. Vorliegend bestreite der Schuldner - wie im Übrigen schon in einem früheren Rechtsöffnungsverfahren in der gleichen Angelegenheit - die Zustellung und damit die gehörige Eröffnung des Einspracheentscheides in nicht haltloser Weise. Obwohl der EStV aus jenem Verfahren die Beweispflicht im Bestreitungsfall bekannt sei, habe sie es erneut unterlassen, entsprechende Belege einzureichen.
Vor diesem Hintergrund hat jedenfalls nicht erst der erstinstanzliche Entscheid dazu Anlass gegeben, den Zustellnachweis für den Einspracheentscheid nunmehr im bundesgerichtlichen Verfahren nachzureichen, weshalb dieser als unzulässiges neues Beweismittel keine Berücksichtigung finden kann (Art. 99 Abs. 1 BGG) und die Zustellbehauptung unbelegt bleibt.
3. In der Sache selbst macht die EStV geltend, der Rechtsöffnungsrichter habe zu Unrecht einen speziellen Zustellnachweis für den Einspracheentscheid verlangt, sei doch die Feststellung der rechtsgenüglichen Zustellung bereits in der von ihr auf dem Entscheid angebrachten Rechtskraftbescheinigung enthalten.
3.1 Soweit die EStV in diesem Zusammenhang vorbringt, gemäss Art. 81 Abs. 1 SchKG dürfe der Schuldner nur Tilgung, Stundung und Verjährung geltend machen, wofür er die Beweislast trage, gehen ihre Ausführungen an der Sache vorbei: Der Schuldner hat bestritten, den als definitiven Rechtsöffnungstitel angerufenen Entscheid erhalten zu haben, weshalb nicht eine Einwendung im Sinn von Art. 81 SchKG, sondern das Vorliegen eines gültigen Rechtsöffnungstitels für die betriebene Forderung zur Diskussion steht.
3.2 Nicht einzutreten ist auf die Beschwerden, soweit die EStV in Bezug auf diese Frage eine offensichtlich unrichtige Sachverhaltsfeststellung geltend macht (Art. 97 Abs. 1 BGG). Ob die blosse Rechtskraftbescheinigung genügt oder ob der Rechtsöffnungsrichter zusätzlich einen konkreten Zustellnachweis verlangen darf, ist keine Sachverhaltsfrage. Vielmehr geht es um die Rechtsfrage, was für Anforderungen an einen Entscheid in qualitativer Hinsicht zu stellen sind, damit ein definitiver Rechtsöffnungstitel im Sinn von Art. 80 Abs. 1 SchKG vorliegt.
3.3 Beruht die Forderung auf einem vollstreckbaren gerichtlichen Urteil, so kann der Gläubiger beim Richter gestützt auf Art. 80 Abs. 1 SchKG die Aufhebung des Rechtsvorschlages (definitive Rechtsöffnung) verlangen; den gerichtlichen Urteilen sind gemäss Art. 80 Abs. 2 Ziff. 2 SchKG auf Geldzahlung gerichtete Verfügungen und Entscheide von Verwaltungsbehörden des Bundes gleichgestellt. Vorliegend geht es um die Frage, was für Anforderungen an einen Entscheid zu stellen sind, damit er vollstreckbar im Sinn von Art. 80 Abs. 1 SchKG ist.
Nach konstanter bundesgerichtlicher Rechtsprechung entfalten Entscheide, die der betroffenen Person nicht eröffnet worden sind, grundsätzlich keine Rechtswirkungen (<ref-ruling> E. 3a/bb S. 99) bzw. erwachsen sie jedenfalls nicht in Rechtskraft (<ref-ruling> E. 1.3 S. 400). Bei Bestreitung der Eröffnung bzw. des Erhalts einer Verfügung oder eines Entscheides trägt die Behörde die Beweislast für die Zustellung (<ref-ruling> E. 4 S. 55; <ref-ruling> E. 3b S. 100). Geht es um eine auf Geld lautende Verfügung oder Entscheidung, hat grundsätzlich der Gläubiger, der einen Rechtsöffnungstitel vorlegt und gestützt hierauf die Erteilung der definitiven Rechtsöffnung verlangt, den - die korrekte Eröffnung voraussetzenden - Nachweis der Vollstreckbarkeit im Sinn von Art. 80 Abs. 1 SchKG zu erbringen. Dieser Beweis lässt sich nicht mit einer blossen Rechtskraftbescheinigung führen (<ref-ruling> E. 2b S. 45; Staehelin, Basler Kommentar, N. 55 und 124 zu Art. 80 SchKG; Eiholzer, Steuern und definitive Rechtsöffnung, in: Richter und Verfahrensrecht, Bern 1991, S. 80 f.).
Was den Bereich der Steuern im Besonderen anbelangt, gelten die genannten Grundsätze nicht nur im Bereich der gewöhnlichen Steuerveranlagung, wo die Veranlagungsverfügungen als Massensendung erfahrungsgemäss nicht mit eingeschriebener Post versandt werden, sondern auch für den Bereich der Einspracheentscheide. Es mag zwar der Usanz entsprechen, dass diese im Unterschied zu den Veranlagungsverfügungen mit eingeschriebener Post versandt werden. Indes sind keine Normen ersichtlich, die ein solches Vorgehen vorschreiben würden; vielmehr sehen die anwendbaren Verfahrensbestimmungen lediglich die Schriftform vor (vgl. Art. 63 Abs. 2 MWStG i.V.m. Art. 34 Abs. 1 VwVG). Sodann ist nicht zu übersehen, dass der Schuldner für die Nichtzustellung a priori keinen Beweis erbringen kann, während die Präsentation des Zustellnachweises der eröffnenden Behörde keinen Aufwand verursacht. Liesse man für den Nachweis der Vollstreckbarkeit die blosse Rechtskraftbescheinigung genügen, so würde diese im Übrigen zur eigentlichen Zustellfiktion, die vom Schuldner selbst dann nicht umgestossen werden könnte, wenn beispielsweise die Sendung auf dem Postweg verloren gegangen oder die Rechtskraftbescheinigung irrtümlich erfolgt sein sollte. Vor diesem Hintergrund haben die kantonalen Gerichte nicht gegen Bundesrecht verstossen, wenn sie angesichts der Bestreitung der Zustellung durch den Schuldner für den als definitiven Rechtsöffnungstitel angesprochenen Entscheid einen speziellen Zustellnachweis verlangt haben.
4. In ihrer gegen den obergerichtlichen Entscheid gerichteten Beschwerde macht die EStV sodann eine Verletzung des rechtlichen Gehörs geltend, was sie bereits in ihrer Nichtigkeitsbeschwerde an das Obergericht gerügt hatte. Sie bringt vor, indem der erstinstanzliche Rechtsöffnungsrichter kein schriftliches Verfahren durchgeführt habe, hätte sie zu den Einwänden des Schuldners keine Stellung nehmen können, was ihren Anspruch auf rechtliches Gehör verletze.
Mit ihrer neuen und damit ohnehin unzulässigen Tatsachenbehauptung, bei über 10'000 Rechtsöffnungsverfahren pro Jahr könne sie unmöglich immer einen Mitarbeiter delegieren, überspielt sie, dass sie in ihrem Gesuch vom 15. März 2007 an die erste Instanz lediglich festgehalten hatte, die mit dem Dossier befasste Mitarbeiterin könne an der Verhandlung vom 30. März 2007 wegen anderweitiger Verpflichtungen am späten Vormittag nicht teilnehmen, und die kantonalen Instanzen befunden haben, angesichts der Grösse der EStV hätte ohne weiteres auch ein anderer Mitarbeiter am Verfahren teilnehmen können.
Wenn die EStV schliesslich behauptet, es sei ihr nicht zuzumuten, den Zustellnachweis jeweils schon dem Rechtsöffnungsgesuch beizulegen, was das Obergericht verkannt habe, unterschlägt sie, dass dieses erwogen hat, der Zustellnachweis hätte insbesondere auch mit der Gesuchseingabe vom 15. März 2007 eingereicht werden können, in welcher sie ausführlich darauf Bezug genommen habe. In der Tat widerspricht es dem in jedem Prozessrechtsverhältnis zum Tragen kommenden Gebot von Treu und Glauben, wenn sich die EStV in ihrem Gesuch um Durchführung eines schriftlichen Verfahrens ausführlich über Modalitäten und Hergang der Zustellung geäussert hat, ohne den Zustellnachweis beizubringen. Im Übrigen war der EStV aus früheren Verfahren bekannt, dass das Bezirksgericht nur bei Vorliegen des Zustellnachweises Rechtsöffnung erteilen würde (vgl. oben, E. 2).
Unter diesen Umständen hat sich die EStV ihre Unterlassung selbst zuzuschreiben. Eine Gehörsverletzung ist vor dem geschilderten Hintergrund jedenfalls nicht ersichtlich, umso weniger als der erstinstanzliche Rechtsöffnungsrichter angedroht hat, bei Nichterscheinen werde aufgrund der Akten entschieden, und der EStV bewusst war, dass sie den Zustellnachweis nicht zu den Akten gegeben hatte.
5. Zusammenfassend ergibt sich, dass die Beschwerden abzuweisen sind, soweit darauf eingetreten werden kann. Der Bund ist in seinen Vermögensinteressen betroffen, weshalb ihm ausgangsgemäss die Gerichtskosten aufzuerlegen sind (Art. 66 Abs. 1 und 4 BGG). Der Gegenpartei ist kein entschädigungspflichtiger Aufwand entstanden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerdeverfahren Nrn. 5A_264/2007 und 5A_495/2007 werden vereinigt.
2. Die Beschwerden werden abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten von Fr. 4'000.-- werden der Schweizerischen Eidgenossenschaft auferlegt.
4. Dieses Urteil wird den Parteien, dem Obergericht des Kantons Zürich und dem Bezirksgericht Zürich schriftlich mitgeteilt.
Lausanne, 25. Januar 2008
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: