Sachverhalt:
A. Das Obergericht des Kantons Zürich verurteilte X._ am 2. Juni 2003 wegen mehrfacher Erschleichung einer Falschbeurkundung gemäss Art. 15 Ziff. 1 Abs. 2 VStrR, wegen mehrfacher Zollübertretung sowie wegen mehrfacher Hinterziehung oder Gefährdung der Steuern gemäss Art. 77 der Mehrwertsteuerverordnung zu einer Busse von Fr. 23'000.--. Dem Schuldspruch liegen drei Ausfuhrabfertigungen für Schmuckwaren im Gesamtwert von Fr. 595'000.-- zu Grunde, bei denen X._ andere als in den Zolldeklarationen angegebene, aber ähnlich aussehende Schmuckstücke mitführte. Drei weitere gleichartige Handlungen erachtete das Obergericht als verjährt. Es trat deshalb in diesen Punkten auf die Anklage nicht ein.
B. X._ erhebt beim Bundesgericht eidgenössische Nichtigkeitsbeschwerde mit dem Antrag, es sei das Urteil des Obergerichts aufzuheben, soweit es ihn auch für die Handlung vom 1. Januar 1996 wegen Erschleichens einer Falschbeurkundung schuldig spreche und bestrafe.
Das Kassationsgericht des Kantons Zürich wies am 21. April 2004 die Beschwerde, die X._ gegen das obergerichtliche Urteil auch bei dieser Instanz einreichte, ab, soweit es darauf eintrat.
Das Obergericht, die Staatsanwaltschaft des Kantons Zürich, die Eidgenössische Zollverwaltung Oberzolldirektion sowie die Schweizerische Bundesanwaltschaft haben auf Gegenbemerkungen zur Beschwerde verzichtet.

Das Bundesgericht zieht in Erwägung:
1. Streitgegenstand des vorliegenden Verfahrens bildet einzig die Frage, ob das dem Beschwerdeführer vorgeworfene Erschleichen einer Falschbeurkundung vom 1. Januar 1996 verjährt ist.
Die Vorinstanz legt zutreffend dar, dass das fragliche Delikt gemäss Art. 15 Ziff. 1 Abs. 2 VStrR ein Vergehen darstellt, bei dem nach den im Tatzeitpunkt geltenden Art. 70 und 72 Ziff. 2 Abs. 2 aStGB in Verbindung mit Art. 2 VStrR die absolute Verjährung nach siebeneinhalb Jahren eintritt. Da die Verjährungsfrist somit bis am 1. Juli 2003 lief, war bei Fällung und Eröffnung des angefochtenen Entscheids am 2. Juni 2003 die umstrittene Handlung nach der zur Tatzeit geltenden Regelung noch nicht verjährt.
Die seit dem 1. Oktober 2002 geltenden neuen Bestimmungen über die Verjährung finden freilich auch auf Taten Anwendung, die vor ihrem Inkrafttreten verübt wurden, wenn sie für den Täter milder sind (<ref-law>; <ref-ruling> E. 5.1 S. 51). Nach <ref-law> in der seit dem 1. Oktober 2002 geltenden Fassung verjährt die am 1. Januar 1996 erschlichene Falschbeurkundung nach sieben Jahren, also am 2. Januar 2003. Allerdings sieht das neue Recht in <ref-law> vor, dass die Verjährung nicht mehr eintritt, wenn vor dem Fristablauf ein erstinstanzliches Urteil ergangen ist.
In der hier umstrittenen Sache fällte der erstinstanzliche Richter am 11. Dezember 2002 das Urteil. Er eröffnete es jedoch nicht mündlich, sondern stellte es dem Rechtsvertreter des Beschwerdeführers am 30. Januar 2003 zu. Dieser nahm den Entscheid am 2. Februar 2003 in Empfang. Vorliegend war am 1. Januar 2003, als die Verjährungsfrist ablief, das erstinstanzliche Urteil wohl gefällt, aber den Parteien noch nicht eröffnet. Der Eintritt der Verjährung hängt hier somit davon ab, ob ein bereits gefälltes, aber noch nicht eröffnetes Urteil als ergangen im Sinne von <ref-law> anzusehen ist.
2. Der Beschwerdeführer macht geltend, die Vorinstanz sei zu Unrecht vom Grundsatz abgewichen, dass ein Urteil erst mit seiner Eröffnung rechtlich wirksam werde. Die Mitteilung an die Parteien bilde den letzten Akt des erstinstanzlichen Prozesses. Es sei deshalb folgerichtig, dass auch dieser letzte Schritt vor Ablauf der Verjährungsfrist abgeschlossen sein müsse. Nur so sei sichergestellt, dass der verjährungsrechtlich massgebende Zeitpunkt mit dem Beginn der Frist für das Ergreifen von Rechtsmitteln zusammenfalle und so eine übersichtliche und kohärente Ordnung entstehe. Andernfalls könnte auch ein Urteil, das erst längere Zeit nach seiner Fällung eröffnet wird, noch Wirkungen entfalten, was dem Grundgedanken der Verjährung zuwiderliefe. Wegen der unterschiedlichen Sachlage könne die Rechtsprechung zur retrospektiven Konkurrenz, bei der das Bundesgericht auf den Zeitpunkt der Fällung und nicht jenen der Eröffnung abstelle (<ref-ruling> E. 1.2), nicht auf den vorliegenden Fall übertragen werden.
2.1 Die Frage, ab welchem Zeitpunkt ein Urteil die Beendigung des Laufs der Verjährung bewirkt, stellte sich schon unter dem alten Recht. Nach Art. 70 und 72 aStGB mussten Verurteilungen vor Ablauf der - relativen oder absoluten - Verjährungsfrist erfolgen und waren nachher nicht mehr zulässig. In diesem Zusammenhang war ebenfalls die Frage zu beantworten, in welchem Zeitpunkt das vor Ablauf der Verjährungsfrist auszusprechende rechtskräftige Strafurteil ergangen war, ob dies bereits mit der Fällung oder erst mit der Eröffnung zutraf.
Die bisherige Rechtsprechung erklärt den Zeitpunkt der Fällung für massgebend. Denn danach könne ein Urteil gemäss dem Grundsatz "lata sententia iudex desinit iudex esse" nicht mehr abgeändert werden. Da der Richter auf ein einmal gefälltes Urteil somit im Prinzip nicht mehr zurückkommen könne, spiele der Zeitpunkt der Mitteilung an die Parteien verjährungsrechtlich keine Rolle (<ref-ruling> E. 2 S. 65 f.). Es wird ebenfalls darauf hingewiesen, dass bei der schriftlichen Mitteilung der Zeitpunkt der Eröffnung in einem gewissen Ausmass vom Verhalten der Parteien abhänge und nicht mehr der Strafverfolgung zugerechnet werden könne (<ref-ruling> E. 3 S. 394; <ref-ruling> E. b S. 172 mit Verweis auf ältere unpublizierte Entscheide).
Allerdings ist es nicht völlig ausgeschlossen, dass der Richter auf ein gefälltes Urteil, das noch nicht mitgeteilt ist, zurückkommt (vgl. für das zürcherische Recht Richard Frank/Hans Sträuli/Georg Messmer, Kommentar zur zürcherischen Zivilprozessordnung, 3. Aufl. Zürich 1997, § 190 N. 3 und 8; in diesem Sinn ferner <ref-ruling> E. 3a/bb S. 99; strenger demgegenüber <ref-ruling> E. 1.2 S. 116; Jean-François Poudret, Commentaire de la loi fédérale d'organisation judiciaire, Band I, Bern 1990, Art. 38 Ziff. 6; vgl. auch Werner Wichser, Tücken der Unabänderlichkeit eines Gerichtsurteils, SJZ 93/1997 S. 171 ff.). Das Bundesgericht hat bereits erklärt, dass eine allfällige Abänderungsmöglichkeit der Entscheide vor ihrer Eröffnung die angeführte Praxis nicht in Frage stellt. Im Fall des Rückkommens auf ein gefälltes, aber noch nicht mitgeteiltes Urteil endet der Lauf der Verjährung erst mit dem Datum der nachträglichen Abänderung, d.h. die Modifikation muss noch vor Eintritt der Verjährung erfolgen (<ref-ruling> E. 3 S. 395).
Die nachgezeichnete Rechtsprechung zur alten gesetzlichen Regelung ist von der Doktrin, soweit sie überhaupt darauf einging, kommentarlos oder zustimmend übernommen worden (vgl. etwa Niklaus Schmid, Strafprozessrecht, 4. Aufl. Zürich/Basel/Genf 2004, N. 585 Anm. 86; Hans Schultz, ZBJV 103/1967 S. 430 f.; Elisabeth Trachsel, Die Verjährung gemäss den Art. 70-75bis des schweizerischen Strafgesetzbuches, Diss. Zürich 1990, S. 178). Da beim Erlass der neuen Bestimmungen über die Verjährung dieser Fragenkreis nicht diskutiert wurde und sich in den Gesetzesmaterialien keine Äusserungen dazu finden, liegt es nahe, die bisherige Praxis auch unter dem neuen Recht weiterzuführen. Dies drängt sich jedenfalls auf, soweit nicht triftige Gründe dagegen sprechen.
2.2 Der Beschwerdeführer verweist auf einen neueren Entscheid des Bundesgerichts, der ein Abrücken von der bisherigen Praxis zu markieren scheint. Tatsächlich wurde in einer Zivilrechtsstreitigkeit erklärt, das Verfahren werde nicht bereits mit der Fällung des Urteils durch den Spruchkörper, sondern erst mit dessen Eröffnung beendigt. Weiter wird ausgeführt, das Urteil "n'existe légalement qu'une fois qu'il a été officiellement communiqué aux parties. Tant qu'il ne l'a pas été, il est inexistant (Nichturteil), il n'est qu'un projet" (<ref-ruling> E. 3a/bb S.99).
Diese Erwägungen, die mit Blick auf ein Urteil erfolgten, das überhaupt nie eröffnet wurde, können nicht verallgemeinert werden. Der Beschwerdeführer legt selber zutreffend dar, dass der Zeitpunkt der Urteilswirkungen nicht generell, sondern nur mit Blick auf den jeweiligen Fragenkreis zu beurteilen ist. Dabei sind auch praktische Aspekte des Verfahrensablaufs mitzuberücksichtigen.
2.3 Es ist zwar davon auszugehen, dass Urteile Wirksamkeit nur erlangen können, wenn sie überhaupt jemals eröffnet werden. Soweit eine Mitteilung an die Parteien erfolgt, steht aber nichts entgegen, einzelne Urteilswirkungen auf den Zeitpunkt der Entscheidfällung zurückzubeziehen. Das kann sich deshalb aufdrängen, weil der Richter von den Verhältnissen im Zeitpunkt der Fällung des Urteils ausgehen muss und er die Eröffnung - namentlich bei schriftlicher Mitteilung - nur beschränkt selber steuern kann. Die Beurteilung, ob eine Straftat verjährt ist, kann der Richter nur bezogen auf den Zeitpunkt, in dem er seinen Entscheid trifft, vornehmen. Denn bei schriftlicher Eröffnung weiss er zum Voraus nicht genau, wann dem Angeschuldigten das Urteil zugestellt wird. Dementsprechend könnte er unter Umständen gar nicht beurteilen, ob bei der schriftlichen Eröffnung die Verjährung einer Straftat eingetreten wäre, wenn auf diesen Zeitpunkt abgestellt werden müsste. Aus diesem Grund stellt die jüngste Rechtsprechung auch bei der sog. retrospektiven Konkurrenz darauf ab, ob die nachträglich zu beurteilenden Taten begangen wurden, bevor das Urteil gefällt und nicht bevor es eröffnet wurde (<ref-ruling> E. 1.2 S. 116).
Aus diesen Erwägungen ist bei der Beurteilung der Frage, wann ein erstinstanzliches Urteil gemäss <ref-law> ergangen sei, an die dargestellte bisherige Praxis anzuknüpfen. Dementsprechend endet der Lauf der Verjährung bereits mit der Fällung und nicht erst mit der Eröffnung des erstinstanzlichen Urteils. Allerdings ist zu präzisieren, dass dies nur unter der Voraussetzung gilt, dass das Urteil überhaupt je eröffnet wird. Ausserdem wäre von der genannten Regel abzuweichen, wenn zwischen der Fällung und Eröffnung ein so grosser Zeitraum läge, dass er mit Blick auf die Dauer der massgeblichen Verjährungsfrist nicht ausser Acht gelassen werden kann. Ein solcher Ausnahmefall ist vorliegend indessen nicht gegeben, erfolgte doch die Eröffnung wenige Wochen nach der Fällung des Urteils.
3. Die Nichtigkeitsbeschwerde erweist sich demnach als unbegründet und ist abzuweisen.
Bei diesem Ausgang sind die Kosten des bundesgerichtlichen Verfahrens dem Beschwerdeführer aufzuerlegen (Art. 278 Abs. 1 BStP).

Demnach erkennt das Bundesgericht:
1. Die eidgenössische Nichtigkeitsbeschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft des Kantons Zürich, der Eidgenössischen Zollverwaltung Oberzolldirektion, der Schweizerischen Bundesanwaltschaft und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 20. September 2004
Im Namen des Kassationshofes
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: