Sachverhalt:
A. X._ wurde Ende Mai 2002 von seiner Arbeitgeberin mit der Begründung entlassen, verschiedene Mitarbeiterinnen und Mitarbeiter, deren Namen ihm nicht mitgeteilt wurden, hätten ihn der sexuellen Belästigung bezichtigt. X._ liess die Arbeitgeberin umgehend wissen, dass er die Kündigung als missbräuchlich erachte, den Kündigungsgrund als ehrverletzend empfinde und sich rechtliche Schritte vorbehalte.
Am 3. Juli 2002 wurde dem Rechtsvertreter von X._ Einsicht in die internen Unterlagen der Arbeitgeberin gewährt, aus welchen er die Namen der Personen, welche die Vorwürfe erhoben hatten, ersehen konnte. Er musste sich jedoch dazu verpflichten, seinem Klienten die entsprechenden Namen nicht bekannt zu geben, woran er sich hielt.
Spätestens am 26. Juli 2002 bevollmächtigte X._ seinen Rechtsvertreter zur vollumfänglichen Wahrung seiner Interessen, einschliesslich der Stellung eines Strafantrages wegen Ehrverletzung gegen die ihn beschuldigenden Personen. Gleichentags ersuchte der Rechtsvertreter die Arbeitgeberin schriftlich darum, seinem Klienten die Namen der entsprechenden Personen bekannt geben zu dürfen, wozu diese mit Schreiben vom 13. August 2003 einwilligte.
B. Am 13. November 2002 reichte X._ beim Bezirksgericht Zürich Ehrverletzungsklage gegen Y._ ein. Mit Beschluss vom 7. Februar 2003 trat das Gericht auf die Klage infolge Verspätung nicht ein. Einen dagegen erhobenen Rekurs wies das Obergericht des Kantons Zürich mit Beschluss vom 20. Juni 2003 ab.
Auf eine gegen den Entscheid des Obergerichts eingereichte kantonale Nichtigkeitsbeschwerde ist das Kassationsgericht des Kantons Zürich mit Beschluss vom 7. Mai 2004 nicht eingetreten.
C. X._ führt eidgenössische Nichtigkeitsbeschwerde mit dem Antrag, der Beschluss des Obergerichts des Kantons Zürich sei aufzuheben.
Y._ beantragt in ihrer Stellungnahme vom 26. Juli 2004 die vollumfängliche Abweisung der Nichtigkeitsbeschwerde, soweit darauf eingetreten werden könne.

Das Bundesgericht zieht in Erwägung:
1. Im Verfahren der eidgenössischen Nichtigkeitsbeschwerde ist der Kassationshof an die tatsächlichen Feststellungen der kantonalen Behörde gebunden (Art. 277bis Abs. 1 BStP). Ausführungen, die sich dagegen richten, sind unzulässig (Art. 273 Abs. 1 lit. b BStP).
Der Beschwerdeführer kritisiert die Sachverhaltsermittlung durch die Vorinstanz als willkürlich. So hält er insbesondere fest, das Gericht sei zu Unrecht davon ausgegangen, dass er seinen Rechtsvertreter bereits vor dem 26. Juli 2002 zur Stellung von Strafanträgen gegen die ihn beschuldigenden Personen mandatiert habe. Entgegen der Auffassung der Beschwerdegegnerin kann aus seinen Ausführungen indes nicht geschlossen werden, dass er vom Bundesgericht verlangt, den vorinstanzlichen Entscheid aus diesem Grund aufzuheben. Wie aus der Beschwerdebegründung klar erhellt, will er damit lediglich darlegen, weshalb er gegen den Beschluss auch kantonale Nichtigkeitsbeschwerde beim Kassationsgericht des Kantons Zürich eingereicht hat. Seiner rechtlichen Argumentation legt er in der Folge ausdrücklich den Sachverhalt zugrunde, wie ihn die Vorinstanz festgestellt hat. Auf sein Rechtsmittel ist daher vollumfänglich einzutreten.
2. Der Beschwerdeführer macht geltend, die Vorinstanz habe <ref-law> verletzt, indem sie davon ausgegangen sei, zum Zeitpunkt der Einreichung seiner Klage sei die Frist, um Strafantrag zu stellen, bereits abgelaufen gewesen. Für den Beginn des Fristenlaufs könne frühestens auf das Datum der Entbindung seines Rechtsvertreters von der Stillhaltevereinbarung, mithin auf den 13. August 2002, abgestellt werden.
2.1 Die dreimonatige Strafantragsfrist beginnt mit dem Tag, an welchem dem Antragsberechtigten der Täter bekannt wird (<ref-law>). Die Antragsberechtigung richtet sich dabei nach dem Träger des angegriffenen Rechtsgutes; bei höchstpersönlichen Rechtsgütern wie der Ehre ist Verletzter nur der Träger des Rechtsgutes selbst (<ref-law>; <ref-ruling> E. 2b).
Das Recht, Strafantrag zu stellen, ist grundsätzlich höchstpersönlicher Natur und unübertragbar (<ref-ruling> E. 3c). Daraus hat das Bundesgericht gefolgert, dass unter dem Antragsberechtigten nur der Verletzte persönlich und nicht auch sein bevollmächtigter Vertreter zu verstehen ist, sodass die Antragsfrist erst zu laufen beginnt, wenn der Verletzte persönlich die Tat und den Täter kennt und nicht schon, wenn sein bevollmächtigter Vertreter diese Kenntnis hat (<ref-ruling> E. 2, 97 I 769 E. 2).
2.2 Nach Auffassung der Vorinstanzen rechtfertigt sich ein Abweichen von der dargelegten Rechtsprechung im vorliegenden Fall deshalb, weil der Beschwerdeführer seinen Rechtsvertreter schon vor dem Zeitpunkt, in welchem er Kenntnis vom Namen der Beschwerdegegnerin erhielt, mit der Stellung eines Strafantrages beauftragt hatte. Er habe sich dessen Kenntnis somit spätestens ab dem 26. Juli 2002 - dem Datum der Bevollmächtigung - anrechnen zu lassen, weshalb die Antragsfrist spätestens am 26. Oktober 2002 abgelaufen sei.
Die Vorinstanzen stützen ihre Ansicht auf Rehberg und Riedo. Rehberg vertritt ohne weitere Begründung die Auffassung, auf die Kenntnis des bevollmächtigten Vertreters müsse es entgegen der bundesgerichtlichen Rechtsprechung ankommen, wenn der Verletzte diesen bereits zu einem Zeitpunkt zur Stellung eines Strafantrages ermächtigt habe, in welchem der Täter noch keinem von beiden bekannt gewesen sei (Jörg Rehberg, Der Strafantrag, ZStrR 85 (1969) S. 247 ff., 269). Riedo teilt diese Meinung und schlägt vor, die Grundsätze anzuwenden, wie sie für das Handeln von Organen juristischer Personen gelten. Es sei stossend, wenn der Vertretene zur Wahrung seiner Interessen einen Vertreter bestellen könnte, um sich später darauf zu berufen, er selbst habe den Täter nicht gekannt (Christof Riedo, Basler Kommentar - Strafgesetzbuch I, Art. 29 N 10).
2.3 Entgegen der Meinung der zitierten Autoren ist kein zwingender Grund ersichtlich, in Fällen wie dem vorliegenden von der bisherigen Rechtsprechung abzuweichen und dem Vertretenen die Kenntnis seines Bevollmächtigten anzurechnen. Denn auch wenn ein Verletzter seinen Rechtsvertreter vor Kenntnis des Täters mit der Einreichung eines Strafantrags beauftragt, ist es durchaus denkbar, dass er, je nachdem, wer als Täter identifiziert wird, keine Strafverfolgung wünscht. Der Entscheid, Strafantrag zu stellen oder darauf zu verzichten, muss ihm daher persönlich erhalten bleiben. Weil der Vertretene, der Strafantrag stellen möchte, im Allgemeinen an einer möglichst baldigen Anhandnahme der Strafverfolgung interessiert sein dürfte, ist die Gefahr des Rechtsmissbrauchs gering. Im Einzelfall könnte einem solchen ohnehin Rechnung getragen werden.
Die Rechtslage bei der bürgerlichen Stellvertretung ist sodann keineswegs mit derjenigen bei der Organvertretung vergleichbar, da juristische Personen naturgemäss nicht selbst, sondern nur durch ihre Organe Strafantrag stellen können. Viel eher scheint ein Vergleich mit der gesetzlichen Vertretung urteilsfähiger Entmündigter angebracht. Denn dem gesetzlichen Vertreter steht hier neben dem Verletzten ein selbständiges Antragsrecht zu (vgl. <ref-law>; <ref-ruling> E. 5b). Wie Riedo selbst festhält, führt die Kenntnis des Täters durch den Vertreter in diesen Fällen nicht zum Beginn des Fristenlaufs für den Vertretenen (Riedo, a.a.O., Art. 28 N 29 sowie Art. 29 N 7; vgl. auch Walter Huber, Die allgemeinen Regeln über den Strafantrag im schweizerischen Recht (StGB 28-31), Diss. Zürich 1967, S. 28). Muss sich aber nicht einmal der gesetzlich Vertretene das Wissen seines Vertreters anrechnen lassen, kann sich dies für die gewillkürte Stellvertretung umso weniger rechtfertigen.
Im vorliegenden Fall kommt hinzu, dass sich der Rechtsvertreter des Beschwerdeführers gegenüber dessen Arbeitgeberin vertraglich verpflichtet hatte, seinem Mandanten die Namen der Mitarbeiterinnen und Mitarbeiter, welche die Vorwürfe der sexuellen Belästigung erhoben hatten, zu verschweigen. Solange er an diese Vereinbarung gebunden war, durfte er keine Strafklage gegen die betreffenden Personen einreichen. Denn hierfür hätte er die Namen in der Klageschrift nennen müssen und der Beschwerdeführer hätte sie spätestens durch Teilnahme am Strafprozess erfahren. Würde für die hier zu entscheidende Frage auf die Kenntnis des Rechtsvertreters abgestellt, hätte die Strafantragsfrist demnach vor dem Zeitpunkt zu laufen begonnen, ab welchem Klage eingereicht werden durfte. Die Arbeitgeberin hätte es damit in der Hand gehabt zu entscheiden, wie viel Zeit dem Beschwerdeführer für die Stellung des Antrags verbleiben bzw. ob ihm dies überhaupt noch möglich sein solle. Es kann aber nicht angehen, dass eine unbeteiligte Drittperson die Dauer der Strafantragsfrist verkürzen kann. Das Argument der Beschwerdegegnerin, der Beschwerdeführer habe nach der Entbindung seines Rechtsvertreters von der Stillhalteverpflichtung am 13. August 2002 zur Einreichung der Klage noch genügend Zeit gehabt, überzeugt daher nicht.
2.4 Nachdem der Name der Beschwerdegegnerin dem Beschwerdeführer laut den verbindlichen tatsächlichen Feststellungen der Vorinstanz vor der Aufhebung der Stillhaltevereinbarung nicht bekannt gegeben worden war, begann die Antragsfrist nach den vorstehenden Erwägungen frühestens am 13. August 2002 zu laufen. Mit Einreichung der Klage am 13. November 2002 war die dreimonatige Frist damit auf jeden Fall gewahrt, weshalb sich die Beschwerde als begründet erweist.
3. Demnach ist die Nichtigkeitsbeschwerde gutzuheissen, der Beschluss des Obergerichts aufzuheben und die Sache an die Vorinstanz zurückzuweisen.
Bei diesem Ausgang des Verfahrens wird die Beschwerdegegnerin kostenpflichtig (vgl. Art. 278 Abs. 1 BStP) und ist dem Beschwerdeführer aus der Bundesgerichtskasse eine angemessene Entschädigung zuzusprechen; die Beschwerdegegnerin ist ihr zu entsprechendem Ersatz zu verpflichten (vgl. Art. 278 Abs. 3 BStP).

Demnach erkennt das Bundesgericht:
1. Die Nichtigkeitsbeschwerde wird gutgeheissen, der Beschluss des Obergerichts des Kantons Zürich, III. Strafkammer, aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird der Beschwerdegegnerin auferlegt.
3. Dem Beschwerdeführer wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet; die Beschwerdegegnerin wird verpflichtet der Bundesgerichtskasse dafür Ersatz zu leisten.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 26. August 2004
Im Namen des Kassationshofes
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: