Sachverhalt:
A. Mit Forderungskaufvertrag vom 24. Mai 1988 verkaufte die U._ der V._ AG Forderungen, die ihr gegen W._ Ltd., X._ AG und C._ zustanden, sowie alle sich daraus ergebenden Schadenersatzansprüche, insbesondere auch diejenigen gegen die Y._ AG Sicherheiten und Nebenrechte zum Kaufpreis von CHF 20'206'000.-- ("V._-Forderungen"). Für die V._ AG handelte D._. Der Kauf wurde von B._ finanziert.
Am 13./21. Juni 1988 schlossen B._ als Treugeber und die V._ AG als Treuhänderin einen Treuhandvertrag. Nach diesem Vertrag erwirbt die Treuhänderin für den Treugeber von der U._ die oben aufgeführten "V._-Forderungen". Die Treuhänderin verpflichtete sich, das Treugut gemäss Instruktionen des Treugebers zu verwalten, einzutreiben und geltend zu machen sowie alle Erlöse gemäss Instruktionen des Treugebers zu verwenden. Gemäss diesem Treuhandvertrag war somit B._ der wirtschaftliche Erwerber und neuer Gläubiger der erwähnten Forderungen. Die V._ AG handelte zwar auf Rechnung von B._, nach aussen trat sie aber ausschliesslich in eigenem Namen auf. Die V._ AG beauftragte im Sommer 1988 Rechtsanwalt E._ mit der prozessualen Durchsetzung der zugunsten von B._ treuhänderisch verwalteten Forderungen gegenüber der Y._ AG.
Am 13. Mai 1991 teilte die V._ AG B._ mit, dass sie von der Entwicklung bei der Z._ Holding AG und der damit im Zusammenhang stehenden Verschlechterung seiner Vermögensverhältnisse Kenntnis genommen habe. Sie bitte um Verständnis, dass sie unter diesen Umständen den Treuhandvertrag kündigen müsse, da er keine Gewähr mehr bieten könne, sie vertragsgemäss für alle Ansprüche unter dem Treuhandvertrag schadlos halten zu können. In der Folge suchte die V._ AG einen Käufer für die oben aufgeführten Forderungen, wobei sie diese mit Schreiben vom 26. Juli 1991 A._ (Beschwerdeführer), dem Schwager von B._, zum Preis von Fr. 500'000.-- anbot, der das Angebot noch gleichentags annahm. Mit Datum vom gleichen Tag teilte die V._ AG B._ mit, da er ihren Aufforderungen zur Bezahlung der aufgelaufenen Kosten und zur Sicherstellung allfälliger Prozessentschädigungen nicht nachgekommen sei, sei sie androhungsgemäss gezwungen gewesen, die ihr treuhänderisch überlassenen Vermögenswerte für seine Rechnung zu veräussern. Den Kaufpreis leistete der Beschwerdeführer in folgenden Teilbeträgen: am 31. Juli 1991 Fr. 230'000.--, am 2. August 1991 Fr. 43'645.--, Fr. 75'825.-- und Fr. 24'104.-- sowie am 5. August 1991 Fr. 128'050.--, total Fr. 501'624.--.
Am 23. August 1991 schloss der Beschwerdeführer als Treugeber wie zuvor schon B._ mit der V._ AG als Treuhänderin ebenfalls einen Treuhandvertrag ab.
Nachdem über B._ infolge seiner Insolvenzerklärung am 4. September 1991 der Konkurs eröffnet worden war, versuchte die Konkursverwaltung namens der Konkursmasse B._ (Beschwerdegegnerin) die fraglichen Forderungen von der V._ AG zurückzuerwerben, weil B._ vor dem Verkauf derselben an den Beschwerdeführer der frühere Eigentümer bzw. Gläubiger dieser Forderungen gewesen war. In der Folge schlossen die V._ AG, zwar im eigenen Namen aber auf Rechnung des nicht namentlich genannten Gläubigers der Forderungen, und die Beschwerdegegnerin am 18./19. Januar 1993 eine Vereinbarung ab, wonach die V._ AG sämtliche Ansprüche gegen W._ Ltd., X._ AG und C._ sowie alle Nebenrechte an die Beschwerdegegnerin abtrat. Dabei ging die Beschwerdegegnerin u.a. die Verpflichtung ein, 15 % des Erlöses aus einer allfälligen Veräusserung dieser Forderungen, im Minimum Fr. 1'165'350.--, der V._ AG bzw. dem Treugeber zu überweisen (Ziff. 3b der Vereinbarung). In diesem Zusammenhang stellte die Beschwerdegegnerin die Bedingung, dass keine Zahlungen direkt oder indirekt an den Gemeinschuldner, d.h. an B._, weitergeleitet werden. Im damaligen Zeitpunkt wusste die Beschwerdegegnerin nicht, wer im fraglichen Zeitpunkt der tatsächliche Gläubiger der Forderungen war.
Im November 1993 verwertete die Beschwerdegegnerin die Forderungen gegen W._ Ltd., X._ AG und C._, wobei sie gemäss Beschwerdegegnerin Fr. 10'127'034.-- und gemäss Beschwerdeführer Fr. 10'415'349.05 brutto bzw. Fr. 9'102'468.55 netto erwirtschaften konnte.
Mit Schreiben von 2. Februar 1994 teilte die Beschwerdegegnerin Rechtsanwalt E._ mit, nach Abschluss des Vergleichs mit der V._ AG habe sie erfahren, dass der Schwager von B._ der Erwerber der dem Vergleich zugrunde liegenden Forderungen sei. Bei dieser Sachlage sei anzunehmen, dass das Geld - entgegen der vertraglichen Zusicherung der V._ AG - direkt oder indirekt wieder an B._ fliessen würde, was unter keinen Umständen geschehen dürfe. Konkursverwaltung und Gläubigerausschuss müssten davon ausgehen, dass sie durch die Vertreter der V._ AG getäuscht worden seien. Sie mache die teilweise, einseitige Unverbindlichkeit des Vergleichsvertrages vom 18./19. Januar 1993, nämlich von dessen Ziffern 3b und 7, geltend wegen absichtlicher Täuschung im Sinne von <ref-law>, eventuell wegen Grundlagenirrtums gemäss <ref-law>. Die genannten Vertragsbestimmungen betrachte sie als ungültig.
Am 25. Februar 1994 trat die V._ AG sämtliche Ansprüche aus der Vereinbarung vom 18./19. Januar 1993 an den Beschwerdeführer ab. Der Beschwerdeführer verlangte in der Folge von der Beschwerdegegnerin gemäss der aufgeführten Vereinbarung 15 % von Fr. 9'102'468.55, d.h. Fr. 1'365'370.30.
B. Am 28. März 2001 reichte der Beschwerdeführer beim Bezirksgericht Zürich eine Teilklage ein und beantragte, die Beschwerdegegnerin sei zu verpflichten, den Teilbetrag von Fr. 50'000.-- samt 5 % Zins seit 22. November 1993 zu bezahlen, unter Vorbehalt späterer Teilklagen. Die Beschwerdegegnerin erhob Widerklage auf Feststellung, dass eine Forderung des Beschwerdeführers im Betrag von Fr. 1'365'370.30 zuzüglich Zinsen von 5 % seit 22. November 1992 gegen die Beschwerdegegnerin nicht besteht. Mit Urteil vom 11. Januar 2008 wies das Bezirksgericht die Klage ab und hiess die Widerklage gut.
Dagegen erhob der Beschwerdeführer Berufung an das Obergericht des Kantons Zürich, mit der er sein vor Bezirksgericht gestelltes Rechtsbegehren erneuerte und Abweisung der Widerklage beantragte. Mit Urteil vom 23. Oktober 2008 wies das Obergericht die Hauptklage ab. In Gutheissung der Widerklage stellte es fest, dass keine Forderung des Beschwerdeführers im Betrag von Fr. 1'365'370.30 zuzüglich Zinsen zu 5 % seit 22. November 1992 gegen die Beschwerdegegnerin besteht.
C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, die Beschwerdegegnerin sei zu verpflichten, den Teilbetrag von Fr. 50'000.-- samt 5 % Zins seit 22. November 1993 zu bezahlen, unter Vorbehalt späterer Teilklagen. Die Widerklage sei abzuweisen.
Die Beschwerdegegnerin beantragt, die Beschwerdeanträge des Beschwerdeführers abzuweisen und das Urteil des Obergerichts vom 23. Oktober 2008 zu bestätigen. Das Obergericht verzichtete auf eine Vernehmlassung.

Erwägungen:
1. Damit ein kantonaler Entscheid mit Beschwerde in Zivilsachen angefochten werden kann, muss der Instanzenzug im Kanton erschöpft sein (<ref-law>). Für Rügen, die mit der Beschwerde in Zivilsachen erhoben werden können, darf kein kantonales Rechtsmittel mehr offen stehen (<ref-ruling> E. 1.3 S. 527). Wurde keine kantonale Nichtigkeitsbeschwerde erhoben, so ist daher auf Rügen, die mit diesem Rechtsmittel einer weiteren kantonalen Instanz hätten vorgetragen werden können, mangels Letztinstanzlichkeit des angefochtenen Entscheids nicht einzutreten.
Der Beschwerdeführer hat gegen das Urteil des Obergerichts vom 23. Oktober 2008 keine Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich erhoben. Dennoch macht er eine willkürliche Beweiswürdigung geltend und rügt den vorinstanzlich festgestellten Sachverhalt in zwei Punkten als willkürlich. Die Rüge der aktenwidrigen oder willkürlichen tatsächlichen Annahmen hätte indes dem Kassationsgericht nach <ref-law>/ZH mit Nichtigkeitsbeschwerde vorgetragen werden können. Im vorliegenden Beschwerdeverfahren kann darauf mangels Ausschöpfung des kantonalen Instanzenzuges nicht eingetreten werden.
2. Soweit der Beschwerdeführer eine Verletzung von Bundeszivilrecht geltend macht, ist das Obergerichtsurteil ein kantonal letztinstanzlicher Entscheid. Indessen erscheint fraglich, ob die Beschwerde als rechtsgenüglich begründet betrachtet werden kann, begnügt sich der Beschwerdeführer doch im Wesentlichen mit der Auflistung seiner Standpunkte, anstatt mit seiner Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz anzusetzen. Damit erfüllt er die Begründungsanforderungen an eine Beschwerde in Zivilsachen kaum (<ref-law>; vgl. dazu <ref-ruling> E. 1.4.1/2; Urteil 4A_22/2008 vom 10. April 2008 E. 1). Ohnehin sind seine Vorbringen unbegründet:
3. Der Beschwerdeführer fordert von der Beschwerdegegnerin (unter Nachklagevorbehalt) einen Teilbetrag von Fr. 50'000.-- der vereinbarten 15 %-Beteiligung am Nettoveräusserungserlös der abgetretenen Forderungen gemäss der Vereinbarung vom 18./19. Januar 1993 mit der Begründung, er sei im fraglichen Zeitpunkt der wirtschaftlich Berechtigte bzw. der Gläubiger der betreffenden Forderungen gewesen. Die Vereinbarung vom 18./19. Januar 1993 war zwischen der Beschwerdegegnerin und der V._ AG, die zwar im eigenen Namen aber auf Rechnung des nicht namentlich genannten Gläubigers der Forderungen handelte, abgeschlossen worden.
3.1 Wie schon das Bezirksgericht erachtete es die Vorinstanz als erstellt, dass die Übertragung der "V._-Forderungen" von B._ auf den Beschwerdeführer ein simuliertes Rechtsgeschäft und demzufolge nichtig war. Demnach sei weiterhin B._ (und nicht der Beschwerdeführer) der wirtschaftlich berechtigte Gläubiger an diesen Forderungen geblieben. Die V._ AG sei gegenüber B._ mit Bezug auf diese Forderungen lediglich Treuhänderin gewesen. Infolge der Konkurseröffnung über B._ habe der Treuhandvertrag gestützt auf <ref-law> keine Wirkungen mehr entfalten können. Deshalb habe die V._ AG auch keine Rechte aus der Vereinbarung vom 18./19. Januar 1993 an den Beschwerdeführer zedieren können.
In einer Eventualbegründung erkannte das Obergericht zudem, dass die Vereinbarung vom 18./19. Januar 1993 (bzw. die betreffenden Ziffern) wegen absichtlicher Täuschung und Grundlagenirrtums für die Beschwerdegegnerin unverbindlich sei, weshalb der Beschwerdeführer auch aus diesem Grund keine Rechte aus dieser Vereinbarung herleiten könne.
3.2 Gegen die Hauptbegründung der Vorinstanz bringt der Beschwerdeführer lediglich vor, eine allfällige Simulation von Vorgeschäften (welche nicht vorliege) vermöge die spätere Vereinbarung vom 18./19. Januar 1993 nicht umzustossen. Mit diesem Vergleich seien die vorherigen Unsicherheiten beseitigt worden. Auch sei auf die Geltendmachung weiterer Rechte ausdrücklich und unwiderruflich verzichtet worden.
Mit diesen Behauptungen zeigt der Beschwerdeführer keine Bundesrechtsverletzung auf. Nach den Feststellungen der Vorinstanz ist der Beschwerdegegnerin der ihr obliegende Beweis (vgl. <ref-ruling> E. 4a S. 342 f.) der Simulation der Übertragung der "V._-Forderungen" von B._ auf den Beschwerdeführer gelungen. Davon ist demnach auszugehen (<ref-law>), auch wenn der Beschwerdeführer das Vorliegen einer Simulation in einer Klammerbemerkung bestreitet. Das simulierte Übertragungsgeschäft war demzufolge nichtig (ATF 123 IV 61 E. 5c/cc S. 68; <ref-ruling> E. 5 S. 207). Wenn die Übertragung der "V._-Forderungen" von B._ auf den Beschwerdeführer simuliert und demzufolge nichtig war, wurde der Beschwerdeführer nicht Gläubiger dieser Forderungen und konnte die V._ AG mit der Vereinbarung vom 18./19. Januar 1993 nicht für ihn Rechte begründen, weil er entgegen seiner Behauptung zum fraglichen Zeitpunkt nicht der wirtschaftlich berechtigte Gläubiger der Forderungen war. Die V._ AG konnte dem Beschwerdeführer auch keine Ansprüche aus der Vereinbarung vom 18./19. Januar 1993 abtreten. Denn die V._ AG war gegenüber B._ mit Bezug auf diese Forderungen Treuhänderin. Der Treuhandvertrag wurde indessen zufolge Konkurseröffnung über B._ beendet (<ref-law>). Inwiefern die entsprechenden Erwägungen der Vorinstanz bundesrechtswidrig sein sollen, ist nicht ersichtlich und wird vom Beschwerdeführer nicht dargelegt.
3.3 Da bereits die Hauptbegründung der Vorinstanz die Klagabweisung zu stützen vermag, erübrigt es sich, auf die Einwendungen des Beschwerdeführers gegen die Eventualbegründung einzugehen. Immerhin ist klarzustellen, dass auf den aussergerichtlichen Vergleich die Regeln über die Willensmängel anwendbar sind (<ref-ruling> E. 1.3; <ref-ruling> E.1.2). Die Vorinstanz hat den Grundsatz "pacta sunt servanda" nicht verletzt, indem sie der Beschwerdegegnerin zugestand, dass sie den Vertrag gestützt auf Art. 28 bzw. <ref-law> einseitig unverbindlich erklären konnte.
Der Beschwerdeführer meint, die Beschwerdegegnerin sei darauf zu behaften, dass sie beim Abschluss der Vereinbarung auf die Bekanntgabe des wirtschaftlich berechtigten Gläubigers der betreffenden Forderungen verzichtet hat. Er baut seine Argumentation gegen die Annahme einer Täuschung im Sinne von <ref-law> bzw. eines Grundlagenirrtums im Sinne von <ref-law> auf diesem Umstand auf. Dies kann jedoch keinen Erfolg haben. Denn es trifft nicht zu, dass es der Beschwerdegegnerin egal war, zu wessen Gunsten die vereinbarte Beteiligung am Veräusserungsgewinn fliessen würde. Ebenso wenig bildete die Identität des wirtschaftlich an den Forderungen Berechtigten ein "caput controversum", also einen zweifelhaften Punkt, der gerade verglichen und nach dem Willen der Parteien dadurch endgültig geregelt sein sollte, so dass deswegen die Irrtumsanfechtung ausgeschlossen wäre (BGE <ref-ruling> E.1.2). Die Vorinstanz stellte vielmehr fest, beweismässig sei deutlich erstellt, dass die Beschwerdegegnerin keine Vereinbarung habe abschliessen wollen, durch die direkt oder indirekt ein Geldfluss zugunsten von B._ hätte entstehen können. Dies sei allen am Abschluss der Vereinbarung Beteiligten, namentlich auch der V._ AG vollkommen klar gewesen. Indem der für diese handelnde D._ vorgegeben habe, wirtschaftlich berechtigt an den fraglichen Forderungen sei eine ausländische Gesellschaft, die mit B._ weder direkt noch indirekt etwas zu tun habe, habe er die Beschwerdegegnerin absichtlich getäuscht, weshalb sie die Vereinbarung gestützt auf <ref-law> mit Bezug auf die vereinbarte teilweise Beteiligung am Veräusserungsgewinn einseitig als unverbindlich erklären könne. Damit sei auch rechtsgenüglich erstellt, dass die Beschwerdegegnerin beim Abschluss der Vereinbarung einem wesentlichen Irrtum im Sinne von <ref-law> unterlegen sei, indem sie von dem ihr vorgegebenen (und erkennbar für sie wesentlichen) Sachverhalt ausgegangen sei, der jedoch mit der Wirklichkeit nicht übereingestimmt habe. Diese Erwägungen sind bundesrechtlich nicht zu beanstanden, und der Beschwerdeführer zeigt auch insoweit keine Bundesrechtsverletzung auf.
4. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 12'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 14'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 21. Januar 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Widmer