Sachverhalt: A. A.a Die Eheleute A._ und B._ (Kläger) mieteten am 11. August 1997 von D._ eine 5-Zimmer Wohnung an der Strasse X._ in Y._ auf den 1. Oktober 1997 zu einem Nettomietzins von Fr. 2'950.-- pro Monat. Für die Nebenkosten (Heizung, Warmwasser, Treppenhausreinigung, Antennen- und Kabelfernsehgebühren, Hauswartung, Liftservice, Wasser, Abwasser, allgemeiner Strom sowie Grundgebühr Kehricht) wurden monatliche Akontozahlungen von Fr. 150.-- vereinbart. Auf den 1. Oktober 2001 wurde der Nettomietzins auf Fr. 3'150.-- erhöht, die monatlichen Akontozahlungen aber bei Fr. 150.-- belassen. Der Mietvertrag endete am 31. März 2003. A.b Durch die vom Vermieter beauftragte Liegenschaftenverwaltung erhielten die Kläger während des ganzen Mietverhältnisses jährlich die Abrechnungen über die Nebenkosten. Die erste Nebenkostenabrechnung für den Zeitraum vom 1. April 1997 bis zum 31. März 1998 blieb unangefochten. Über die folgende Abrechnung schlossen die Parteien nach Anfechtung durch die Mieter vor der zuständigen Schlichtungsbehörde einen Vergleich. Darin erklärte sich der Vermieter bereit, "die Heiz- und Nebenkostenabrechnung 1998/1999... neu zu erstellen", und er verpflichtete sich, "einen neuen Verteilschlüssel berechnen zu lassen, der insbesondere auch die Problematik des Wasserverbrauchs der Dachterasse sowie der 2-Zimmerwohnung im UG angemessen berücksichtigt". Dieser neue Verteilschlüssel sollte gemäss dem Vergleich auch auf die Abrechnung 2000/2001 angewendet werden. A.c Die effektiven Nebenkosten beliefen sich jeweils auf mehr als das Doppelte (rund 210-260 %) der geleisteten Akontozahlungen. Die Kläger bezahlten zwar die betreffenden Rechnungen, verlangten hernach aber die Rückzahlung des 20 % ihrer Akontozahlungen übersteigenden Betrages für die Abrechnungsperioden 1998/1999 bis 2002/2003, den sie auf Fr. 10'143.-- bezifferten. Dafür belangten sie C._ als Rechtsnachfolgerin des mittlerweile verstorbenen Vermieters zunächst vor der Schlichtungsbehörde und mit Klage vom 4. Juni 2004 vor dem Mietgericht des Bezirks Zürich. Der Mietgerichtspräsident als Einzelrichter wies die Klage am 18. Januar 2005 ab. Er hielt die Forderung für materiell unbegründet und zudem mit Ausnahme der auf die letzte Mietperiode (April 2002 bis März 2003) entfallenden Rückforderung im Betrag von Fr. 2'064.--für verjährt. A.d Die von den Klägern erhobene Berufung wies das Obergericht des Kantons Zürich am 23. März 2005 unter Bestätigung des erstinstanzlichen Entscheides ab. B. Die Kläger beantragen dem Bundesgericht mit eidgenössischer Berufung, den Beschluss des Obergerichts des Kantons Zürich vom 23. März 2005 aufzuheben und die Beklagte zu verpflichten, ihnen Fr. 10'143.25 zu bezahlen. Die Beklagte schliesst auf Abweisung der Berufung und der Klage. 