Sachverhalt:
A. Die Erben des G.X._, R.X._ und H.X._ (Kläger), vermieteten der Garage A._ AG (Beklagte) Räumlichkeiten im Erdgeschoss, im Keller und in der Hofunterkellerung der Liegenschaften B._strasse .... in Zürich zur Benützung als Autogarage, Autoreparaturwerkstätte, Auto-Einstellhalle und Büro. Das Mietverhältnis geht auf einen zwischen G.X._ und der Rechtsvorgängerin der Beklagten per 1. Januar 1978 abgeschlossenen Mietvertrag zurück. Am 22. Juni 1999 verlangte die Beklagte eine Mietzinsherabsetzung, die sie mit dem gesunkenen Hypothekarzinsfuss begründete. Die Kläger entsprachen diesem Begehren per 1. April 2000. Am 25. Februar 1999 orientierten die Kläger die Beklagte über eine anstehende Renovation an der Liegenschaft B._strasse ..... Die der Beklagten dadurch entstandenen Unannehmlichkeiten und die deswegen von der Beklagten geltend gemachten Schadenersatzansprüche wurden in der Folge verschiedentlich mündlich und schriftlich thematisiert. Im Februar 2000 übermittelte die Beklagte den Klägern eine Liste sämtlicher umbaubedingter Störungen vom 26. Oktober 1999 bis zum 18. Februar 2000. Am 9. März 2000 trafen sich die Parteien zu einer Besprechung, über welche R.X._ ein Protokoll erstellte. Danach vereinbarten die Parteien, dass die Kläger der Beklagten für die verschiedenen renovationsbedingten Störungen, Blockaden, Ausfälle und Umtriebe insgesamt Fr. 2'150.-- bezahlen würde. Ausserdem kamen sie überein, dass die Beklagte die Reparatur der Schäden des Sturms Lothar in Auftrag geben würde und dass sie anschliessend die Entschädigung der Gebäudeversicherung im Betrag von maximal Fr. 10'500.-- erhalten werde.
Der Betrag von Fr. 2'150.-- wurde am 11. April 2000 beglichen. Wegen weiterer Betriebsbeeinträchtigungen aufgrund der Umbauten in der Zeit nach dem 9. März 2000 wurden im August 2000 im Einverständnis mit den Klägern Fr. 2'500.-- von den Mietzinsen und Nebenkosten in Abzug gebracht.
B. Die Kläger kündigten das Mietverhältnis mit amtlichem Formular vom 26. Oktober 2001 auf den 30. September 2002 wegen Nutzungsänderung im Rahmen geänderter Vermietungsstruktur. Hierauf stellte die Beklagte am 21. November 2001 der Schlichtungsbehörde den Antrag, die Kündigung für ungültig zu erklären, dem die Schlichtungsbehörde mit Beschluss vom 8. Februar 2002 entsprach. Das Eventualbegehren der Beklagten um eine längst mögliche Erstreckung des Mietverhältnisses wurde damit gegenstandslos. Das Mietgericht des Bezirks Zürich erklärte jedoch am 9. Oktober 2003 in Gutheissung der Klage die Kündigung vom 26. Oktober 2001 auf den 30. September 2002 für gültig, und es erstreckte das Mietverhältnis erstmals bis und mit 30. September 2004. Das Obergericht des Kantons Zürich, II. Zivilkammer, wies die hiegegen erhobene Berufung der Beklagten ab und bestätigte das Urteil des Bezirksgerichts mit Beschluss vom 19. Februar 2004.
C. Die Beklagte beantragt dem Bundesgericht mit eidgenössischer Berufung, in Aufhebung des obergerichtlichen Beschlusses die Kündigung für ungültig zu erklären. Die Kläger schliessen auf kostenfällige Abweisung der Berufung.

Das Bundesgericht zieht in Erwägung:
1. Wie im kantonalen Verfahren ist vor Bundesgericht einzig streitig, ob die Kündigung innerhalb einer dreijährigen Sperrfrist gemäss Art. 271a Abs. 1 lit. e Ziff. 4 OR erfolgte, weil der Mieter durch Schriftstücke nachwies, dass er sich ausserhalb eines Schlichtungs- oder Gerichtsverfahrens mit dem Vermieter über eine Forderung aus dem Mietverhältnis einigte (<ref-law>). Die Beklagte will in erster Linie eine Änderung der einschlägigen Rechtsprechung des Bundesgerichts über die Auslegung der genannten Bestimmungen bewirken. Als Eventualstandpunkt bringt sie vor, die Vorinstanz habe zu Unrecht erkannt, eine Einigung im Sinne der bundesgerichtlichen Rechtsprechung habe nicht stattgefunden. Diese Rügen sind nachstehend zu behandeln.
2. 2.1 Als Einigung im Sinne von <ref-law> gilt nach der Rechtsprechung des Bundesgerichts, die sich auf die herrschende Lehre stützt, nur eine einvernehmliche Streitbeilegung, mittels der eine unter den Parteien kontroverse Rechtsfrage abschliessend geklärt wird. Das ergibt sich bereits aus dem systematischen Zusammenhang der Norm, welche an <ref-law> anknüpft. Diese Bestimmung soll dem Mieter während drei Jahren seit Abschluss eines Schlichtungs- oder Gerichtsverfahrens Schutz vor einer Rachekündigung seitens des Vermieters gewähren. Ein solches Verfahren setzt notwendigerweise voraus, dass unter den Parteien über Forderungen aus dem Mietverhältnis Uneinigkeit herrschte. Da <ref-law> darauf zielt, dem Mieter denselben Schutz auch ohne Anhebung eines behördlichen Verfahrens zu gewähren, ist auch diese Norm nur unter der Voraussetzung anwendbar, dass zwischen den Parteien vorgängig Differenzen bestanden haben. Für diese Auffassung sprechen ferner die Materialien, war doch bei den Beratungen im Parlament stets von Differenzen, Meinungsverschiedenheiten bzw. Streitigkeiten zwischen Mieter und Vermieter die Rede (Voten Koller, AB 1989 S 430 und 683, AB 1989 N 1879; Votum Bührer, AB 1989 S 430). Nicht von <ref-law> erfasst werden daher Fälle, in denen es gar nicht erst zu einer Auseinandersetzung kommt, weil die eine oder andere Partei dem Begehren des Vertragspartners sogleich entspricht, z.B. wenn der Vermieter seine Forderung auf erstmalige Bestreitung durch den Mieter hin fallen lässt oder umgekehrt einer Forderung seines Mieters umgehend nachkommt. In welchem Masse der Vermieter nachgibt, ist dabei - abgesehen von eigentlichen Bagatellfällen, die keine Sperrfrist auszulösen vermögen (unveröffentlichtes Urteil des Bundesgerichts 4C.266/1993 vom 5. Januar 1994, E. 4a, abgedruckt in: mp 1995 S. 227 f.) - ebenso wenig ausschlaggebend wie im Falle von Art. 271a Abs. 1 lit. e Ziff. 4 OR. Sieht der Mieter seine Anliegen durch die erste Reaktion des Vermieters bereits hinreichend berücksichtigt, kann von der Beilegung eines Streites offensichtlich nicht die Rede sein. Die Auslösung einer dreijährigen Kündigungssperrfrist erscheint in solchen Fällen daher nicht gerechtfertigt (unveröffentlichte Urteile des Bundesgerichts 4C.179/1999 vom 24. August 1999, E. 3b, abgedruckt in: Pra 89/2000 Nr. 29 S. 172 f., 4C.400/1998 vom 23. März 1999, E. 3, abgedruckt in: mp 1999 S. 196, und 4C.266/1993 vom 5. Januar 1994, E. 4a, abgedruckt in: mp 1995 S. 227 f., mit Hinweisen auch auf die abweichenden Meinungen von Anita Thanei, Ausgewählte Entscheide zum Kündigungsschutz, Fachreihe Mietrecht Nr. 4, Zürich 1996, S. 39 f., und Christian Calamo, Die missbräuchliche Kündigung der Miete von Wohnräumen, Diss. St. Gallen 1993, S. 262).
2.2 Diese Rechtsprechung ist in der Lehre auf Zustimmung, jedenfalls, soweit ersichtlich, nicht auf Kritik gestossen (Tissot, in: Droit du bail, 8/1996 S. 35; Futterlieb, in: MietRecht Aktuell 1999 S. 202; Weber, Basler Kommentar, N. 27 zu Art. 271/271a OR; Lachat, Commentaire romand, N. 17 f. zu <ref-law>; Guhl/Koller/Schnyder/Druey, Das Schweizerische Obligationenrecht, 9. Aufl., Zürich 2000, § 44, Rz. 186; Honsell, Schweizerisches Obligationenrecht, Besonderer Teil, 7. Aufl., Bern 2003, S. 240; Tercier, Les contrats spéciaux, 3. Aufl., Zürich 2003, Rz. 2473; Sommer, in: MietRecht Aktuell 1995 S. 42 f., je mit Hinweisen). Entgegen der Auffassung der Beklagten erwähnen auch Lachat/Stoll/Brunner, dass bei einer Einigung ausserhalb eines Schlichtungs- oder Gerichtsverfahrens gleich wie bei einem gerichtlichen Vergleich ein gewisses gegenseitiges Nachgeben notwendig ist (Mietrecht für die Praxis, 4. Aufl., Zürich 1999, S. 548). Zwar führen sie in einer Fussnote dazu aus, nach dem Wortlaut des Gesetzes finde <ref-law> Anwendung, wenn die Vermieterschaft ein schriftlich gestelltes Herabsetzungsgesuch der Mieterschaft akzeptiere (a.a.O., S. 548, Fn. 176). Weshalb aber ein derartiger Vorgang mit sofortiger Zustimmung des Vermieters bereits eine "Einigung" bedeuten soll, legen sie nicht dar und ist nicht ersichtlich. Für eine Neubeurteilung des Wortsinns in Abweichung vom Bundesgerichtsurteil 4C.179/1999 vom 24. August 1999, E. 3b besteht unter diesem Gesichtswinkel kein Anlass.
2.3 Auch in der Sache dringt die mit der Berufung gegen die angeführte Rechtsprechung erhobene Kritik der Beklagten nicht durch. Soweit die Beklagte geltend macht, das Erfordernis des gegenseitigen Nachgebens finde weder im Gesetzeswortlaut noch in den Materialien eine Stütze, übergeht sie die Erwägungen in den von ihr beanstandeten Urteilen, die, wie oben dargestellt (E. 2.1 hiervor), eben diese Fragen abhandeln. Es kann darauf verwiesen werden. Ferner verkennt die Beklagte die ratio legis von <ref-law>, indem sie sich sinngemäss darauf beruft, die Kündigungssperre habe Platz zu greifen, wenn der Vermieter nicht von sich aus die an sich angebrachte Mietzinsherabsetzung vornimmt. Die gesetzliche Regelung bezweckt nämlich nicht, dem Mieter die Geltendmachung seiner Rechte abzunehmen, sondern bloss, ihn davor zu bewahren, dass ihm vermieterseits rechtsmissbräuchlich gekündigt wird, insbesondere, weil er gegen den Willen des Vermieters auf der Durchsetzung berechtigter Forderungen beharrt hat (Weber, a.a.O., N. 3 und 8 f. zu Art. 271/271a OR). Dass es sich inhaltlich beim aussergerichtlichen um etwas anderes als beim gerichtlichen Vergleich handeln soll, geht aus keinem der zitierten Entscheide hervor (zur Definition des aussergerichtlichen Vergleichs <ref-ruling> E. 1c; zum Begriff des gerichtlichen und aussergerichtlichen Vergleichs Vogel/Spühler, Grundriss des Zivilprozessrechts und des internationalen Zivilprozessrechts der Schweiz, 7. Aufl., Bern 2001, 9. Kap., Rz. 52f.). Die Ausführungen der Beklagten, wonach der Begriff der (aussergerichtlichen) Einigung gemäss <ref-law> in gleichem Sinne wie nach Art. 271a Abs. 1 lit. e Ziff. 4 OR zu verstehen sei, fallen deshalb ins Leere. Fehl geht schliesslich der Einwand der Beklagten, bei der aufgrund der Praxis des Bundesgerichts bestehenden Rechtslage werde ein Mieter geradezu verleitet, entweder übersetzte Forderungen aus dem Mietverhältnis zu stellen oder den Richter anzurufen, ohne zuvor an den Vermieter zu gelangen, um in den Genuss der gesetzlichen Kündigungssperre zu gelangen. Bei beiden Verhaltensweisen würde sich die anschliessende Berufung auf die Sperrfrist wohl ihrerseits als rechtsmissbräuchlich erweisen und deswegen ihr Ziel verfehlen (<ref-law>, e contrario; Weber, a.a.O., N. 27 zu Art. 271/271a OR; Lachat, a.a.O., N. 5 zu <ref-law>; Tercier, a.a.O., Rz. 2471). Die Beklagte führt mithin keinerlei stichhaltige Gründe für eine Änderung der Rechtsprechung ins Feld. Diese ist daher zu bestätigen.
3. 3.1 Nach den verbindlichen Feststellungen im angefochtenen Urteil (Art. 63 Abs. 2 OG) war die Frage der Entschädigung der Beklagten wegen Beeinträchtigungen durch die Bautätigkeit im Grundsatz von Beginn an unstreitig. Die Vorinstanz beurteilte auch die Besprechung vom 9. März 2000, die zur Einigung über die Höhe der Entschädigung geführt hat, im Einklang mit dem Bezirksgericht nicht als lang andauernde kontroverse Auseinandersetzung und stellte fest, die geltend gemachten Störungen seien nicht strittig gewesen. Auch aus dem Umstand, dass über das Quantitativ der Entschädigung und über die Zusammensetzung der Teilbeträge anlässlich der Sitzung vom 9. März 2000 diskutiert wurde, hat nach Auffassung der Vorinstanz nicht zwingend zur Folge, dass deshalb als von einer durch Vergleich beigelegten Streitigkeit auszugehen ist. Nach Auffassung der Vorinstanz wäre andernfalls die Vermieterschaft faktisch gezwungen, jegliche mieterseitig gestellte Entschädigungsforderung unbesehen zu akzeptieren, um eine Kündigungssperre zu vermeiden.
3.2 Soweit die Beklagte in der Berufung vorbringt, sowohl die Abmachung vom 9. März 2000 als auch jene über die weitere Zahlung von Fr. 2'500.-- sei erst nach einem längeren Hin und Her, nach hartem, zeitaufwändigem Ringen zustande gekommen, und behauptet, die Kläger seien noch vor Mietgericht der Meinung gewesen, eine freiwillige Leistung erbracht zu haben, kritisiert sie die Beweiswürdigung der Vorinstanz und erweitert den verbindlich festgestellten Sachverhalt. Damit ist sie nicht zu hören (Art. 55 Abs. 1 lit. c und Art. 63 Abs. 2 OG).
3.3 Die Beklagte macht weiter geltend, im vorliegenden Falle hätten Diskussionen mit gegenseitigem Nachgeben stattgefunden. Die Vermieterschaft habe immer wieder genaue Zusammenstellungen der Beeinträchtigungen gefordert. Wegen des erheblichen Ermessensspielraums betreffend das Ausmass einer Mietzinssenkung wegen Umbauarbeiten entstünden hierüber meistens Diskussionen unter den Parteien. Wenn es zu einer Einigung komme, werde eine unklare Rechtslage beseitigt.
Mit diesen Ausführungen vermag die Beklagte keine Verletzung von Bundesrecht aufzuzeigen. Es gehört generell zu den Obliegenheiten eines Ansprechers, gegenüber dem Belangten die Tatsachen klar und detailliert darzulegen, aus denen er das geltend gemachte Recht ableitet. So verhält es sich insbesondere auch in Bezug auf Ansprüche eines Mieters bei laufendem Mietverhältnis, wenn der Vermieterschaft die zur Forderung Anlass bietenden Umstände nicht ohne Weiteres bekannt sein können. Bevor dem Belangten der Forderungsgrund substanziiert bekanntgegeben worden ist, kann sich richtig besehen die Frage, ob die Parteien von Anfang an oder erst nach gegenseitigem Nachgeben über den Bestand des Anspruchs einig waren, gar nicht stellen. Wenn die Kläger daher über die Anspruchsgrundlage bildenden Beeinträchtigungen der Beklagten ins Bild gesetzt werden wollten, um die Höhe der im Grundsatz bereits anerkannten Mietzinsherabsetzung beurteilen zu können, kann darin von vornherein kein Ringen um den angemessenen Betrag erblickt werden. Dass die Parteien auch, als die abzugeltenden Störungen im Gebrauch der Mietsache einmal feststanden, unterschiedliche Vorstellungen in quantitativer Hinsicht zu überwinden hatten, um zu einer Einigung zu gelangen, geht aus dem angefochtenen Urteil nicht hervor. Die Vorinstanz hat somit bundesrechtskonform angenommen, der Abgeltung der baubedingten Unannehmlichkeiten durch die Kläger sei keine Streitbeilegung im Sinne der Rechtsprechung vorausgegangen.
4. Insgesamt erweist sich die Berufung als unbegründet und ist abzuweisen, wobei die Beklagte als unterliegende Partei kosten- und entschädigungspflichtig wird (Art. 156 Abs. 1 und Art. 159 Abs. 1 und 2 OG).

Demnach erkennt das Bundesgericht:
1. Die Berufung wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 6'000.-- wird der Beklagten auferlegt.
3. Die Beklagte hat die Kläger für das bundesgerichtliche Verfahren mit Fr. 7'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 18. Juni 2004
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: