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.