Sachverhalt: A. A._ (Beschwerdeführer) schloss am 22. Mai 2002 als Leasingnehmer mit der X._ AG (Beschwerdegegnerin) einen Leasingvertrag auf 48 Monate über ein Fahrzeug BMW 530iA Limousine zu einem Nettopreis von Fr. 68'760.--. Der erste Leasingzins betrug Fr. 19'000.--, die Monatsraten im Übrigen Fr. 1'147.--. Für den Fall vorzeitiger Kündigung bestimmt Ziff. 15 des Leasingvertrages was folgt: "15.1 Im Falle einer vorzeitigen Vertragsauflösung hat der Leasingnehmer BMW das Fahrzeug nach Ablauf der Kündigungsfrist, bei fristloser Vertragsauflösung sofort zurückzugeben, und es erfolgt eine Schlussabrechnung gemäss nachstehender Aufstellung: 15.2 Verfallene Leasingzahlungen + Verzugszins und Kosten gemäss Ziff. 14.1 + Summe der bis zum Vertragsende noch ausstehenden Leasingzahlungen + Restwert gemäss Kaufvertrag mit dem Lieferanten = BRUTTOFORDERUNG ./. Verminderung um einen marktüblichen Diskont ./. Kaution gemäss Leasingvertrag ./. Fahrzeugwert Eurotax blau, abzüglich Instandstellungskosten, welche durch die Kaskoversicherung nicht gedeckt sind = NETTOFORDERUNG / Schaden BMW 15.3 Bei Streitigkeiten über die Abrechnung der Instandstellungskosten, wird eine neutrale Expertise durch einen neutralen, sachverständigen Fahrzeugexperte - nach und auf Kosten des Leasingnehmers - eingeholt, dessen Entscheid beide Parteien als verbindliches Schiedsgutachten anerkennen. 15.4 Kann das Fahrzeug BMW nicht zurückgegeben werden, erhöht sich der gemäss oben stehender Methode berechnete Schaden noch um den Fahrzeugwert, den das Fahrzeug zum Zeitpunkt der Vertragsauflösung noch aufweisen würde." Beide Parteien sind alsdann ihren vertraglichen Pflichten nachgekommen. Mit Schreiben vom 26. Mai 2003 kündigte der Beschwerdeführer den Leasingvertrag per 31. Juli 2003 vorzeitig und gab den Wagen am 25. Juli 2003 zurück. Gemäss Schlussabrechnung der Beschwerdegegnerin schuldet der Beschwerdeführer ihr noch Fr. 2'851.--, was dieser bestritt. B. Am 17. Mai 2005 klagte der Beschwerdeführer vor dem Bezirksgericht Dielsdorf gegen die Beschwerdegegnerin auf Zahlung von Fr. 34'924.90 nebst Zins und auf Bekanntgabe der Höhe aller Entschädigungen an die Y._ AG für den mit ihm abgeschlossenen Leasingvertrag. Ausserdem sei davon Vormerk zu nehmen, dass es sich um eine Teilklage handle. Mit Urteil vom 17. Juni 2007 verpflichtete das Bezirksgericht die Beschwerdegegnerin, dem Beschwerdeführer Fr. 851.-- zuzüglich 5 % Zins seit 24. August 2004 zu bezahlen. Im Übrigen wies es die Klage ab. Auf Berufung des Beschwerdeführers hin stellte das Obergericht des Kantons Zürich am 14. November 2008 fest, dass das erstinstanzliche Urteil mit Bezug auf die Verpflichtung zur Zahlung von Fr. 851.-- zuzüglich Zins seit 24. August 2004 in Rechtskraft erwachsen ist und wies die Klage im darüber hinausgehenden Betrag ab. C. Der Beschwerdeführer erhebt gegen das Urteil des Obergerichts vom 14. November 2008 Beschwerde in Zivilsachen mit den Begehren, die Beschwerdegegnerin zu verpflichten, ihm Fr. 34'924.90 nebst 5 % Zins seit 24. August 2004 abzüglich rechtskräftig zugesprochener Fr. 851.-- zu bezahlen. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde und Bestätigung des angefochtenen Urteils betreffend den in der Beschwerde gestellten Hauptantrag sowie auf Nichteintreten betreffend den Eventualantrag. Der Beschwerdeführer hat unaufgefordert eine Replik eingereicht, die der Beschwerdegegnerin zugestellt wurde.