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.