Sachverhalt: Sachverhalt: A. A.a Die Swisscom AG, Bern, (Klägerin, Widerbeklagte und Beschwerdegegnerin) wurde 1998 als Aktiengesellschaft gestützt auf das Bundesgesetz über die Organisation der Telekommunikationsunternehmung des Bundes (Telekommunikationsunternehmungsgesetz, TUG) vom 30. April 1997 (SR 784.11) gegründet. Sie führt mit ihrer Errichtung die Anstaltsteile der (ehemaligen) PTT-Betriebe weiter, welche Fernmelde- und Rundfunkdienste erbrachten (Art. 21 Abs. 1 TUG). Sie hat sämtliche Aktiven und Passiven dieser Anstaltsteile übernommen, die bis 1998 unter der Bezeichnung Telecom PTT im Markt auftraten (Art. 23 Abs. 1 TUG). -:- X._ (Beklagter, Widerkläger und Beschwerdeführer) ist Rechtsanwalt sowie Honorarkonsul des Landes A._. Nach eigenen Angaben ist er zur Hauptsache als Geschäftsmann tätig. Danach berät er finanzstarke Privatpersonen und Unternehmen und betreibt die Vermittlung von Geschäften, während die eigentliche Anwaltstätigkeit nur noch untergeordnete Bedeutung habe. A.b Im August 1994 leitete die Regierung des Landes A._ eine Auktion über eine Minderheitsbeteiligung an der damaligen staatlichen Telefongesellschaft Y._ Telecom ein. Am Auktionsverfahren beteiligte sich neben vier anderen Bewerbern ein Joint Venture unter der Firma Z._ N.V., zu dem sich eine ausländische Telefongesellschaft und die Telecom PTT zusammengeschlossen hatten. Der Zuschlag wurde am 28. Juni 1995 bekannt gegeben; Z._ N.V. erwarb eine Beteiligung von 27 % an der Y._ Telecom zum Preis von USD 1.45 Milliarden. A.c Der Beklagte kontaktierte anfangs April 1995 den ehemaligen Generaldirektor der Telecom PTT, B._, und bot ihm seine Dienste im Zusammenhang mit dem Verfahren um die Beteiligung an der Y._ Telecom an. B._ informierte seinen Nachfolger C._, der seinerseits am 4. Mai 1995 mit dem Beklagten telefonisch Kontakt aufnahm. In der Folge traf sich der Beklagte am 19. Juni 1995 und am 22. Juni 1995 mit D._, dem bei der Telecom PTT verantwortlichen Projektleiter für die Ausschreibung Y._ Telecom, zu Gesprächen. Am 22. Juni 1995 verfasste er ein Schreiben an den damaligen Wirtschaftsminister des Landes A._, in dem die Vorteile der Offerte der Z._ N.V. gepriesen wurden. A.d Der Beklagte machte in der Folge geltend, es sei zwischen den Parteien ein Mäklervertrag zustande gekommen. Ausgehend von einem Provisionssatz von 1.5 % verlangte er bezogen auf den Zuschlagspreis von USD 1.45 Mia. einen Mäklerlohn von CHF 22.5 Mio. zuzüglich 7.6 % Mwst. Diese Forderung meldete er am 3. Juli 2002 gemäss Art. 733 OR an, als die Klägerin im Rahmen einer beabsichtigten Kapitalherabsetzung einen Schuldenruf durchführte. A.e Am 1. September 2003 stellte die Klägerin beim Handelsgericht des Kantons Zürich das Begehren, es sei festzustellen, dass sie dem Beklagten nichts schulde (Ziffer 1). Ausserdem beantragte sie, der Beklagte sei zu verpflichten, ihr CHF 47'542.25 nebst Zins zu bezahlen (Ziffer 2.). Diese Forderung betrifft die Kosten, welche die Klägerin für die Sicherstellung der Forderung des Beklagten aufwenden musste, um ihr Aktienkapital mit Beschluss vom 30. April 2002 herabzusetzen. Sie musste für die Bankbürgschaft, deren Abschluss die Parteien am 25. Juli 2002 vereinbarten, nebst einer einmaligen Bearbeitungsgebühr pro Quartal CHF 9'505.45 bezahlen. Sie erhöhte im Laufe des Prozesses ihre Forderung auf CHF 114'080.40 nebst Zins. A.f Der Beklagte erhob Widerklage auf Bezahlung des beanspruchten Mäklerlohnes. Er beantragte mit bereinigtem Rechtsbegehren, die Klägerin und Widerbeklagte sei zu verpflichten, ihm CHF 22'500'000.-- zuzüglich 7.6 % MwSt. und Zins zu 5 % seit 22. Dezember 1995 zu bezahlen. A.f Der Beklagte erhob Widerklage auf Bezahlung des beanspruchten Mäklerlohnes. Er beantragte mit bereinigtem Rechtsbegehren, die Klägerin und Widerbeklagte sei zu verpflichten, ihm CHF 22'500'000.-- zuzüglich 7.6 % MwSt. und Zins zu 5 % seit 22. Dezember 1995 zu bezahlen. B. Das Handelsgericht des Kantons Zürich schrieb mit Beschluss vom 3. Juli 2006 die Klage mit Bezug auf das Klagebegehren Ziffer 1 als gegenstandslos ab. Mit Urteil vom 3. Juli 2006 wies das Gericht die Klage mit Bezug auf das Klagebegehren Ziffer 2 ab (Dispositiv-Ziffer 1). Die Widerklage wurde abgewiesen (Dispositiv-Ziffer 2). Das Handelsgericht kam zum Schluss, das - ursprünglich vorhandene - Feststellungsinteresse der Klägerin sei durch die Widerklage dahingefallen. Die Widerklage wies das Gericht im Wesentlichen aus der Erwägung ab, dass ein Mäklervertrag nicht zustande gekommen und der Aufwand für die Erfüllung des Auftrags nicht nachgewiesen sei. Die Forderung der Klägerin auf Ersatz ihrer Auslagen für die Bürgschaft wies das Handelsgericht ab, weil sie sowohl einer gesetzlichen wie einer vertraglichen Grundlage entbehre. B. Das Handelsgericht des Kantons Zürich schrieb mit Beschluss vom 3. Juli 2006 die Klage mit Bezug auf das Klagebegehren Ziffer 1 als gegenstandslos ab. Mit Urteil vom 3. Juli 2006 wies das Gericht die Klage mit Bezug auf das Klagebegehren Ziffer 2 ab (Dispositiv-Ziffer 1). Die Widerklage wurde abgewiesen (Dispositiv-Ziffer 2). Das Handelsgericht kam zum Schluss, das - ursprünglich vorhandene - Feststellungsinteresse der Klägerin sei durch die Widerklage dahingefallen. Die Widerklage wies das Gericht im Wesentlichen aus der Erwägung ab, dass ein Mäklervertrag nicht zustande gekommen und der Aufwand für die Erfüllung des Auftrags nicht nachgewiesen sei. Die Forderung der Klägerin auf Ersatz ihrer Auslagen für die Bürgschaft wies das Handelsgericht ab, weil sie sowohl einer gesetzlichen wie einer vertraglichen Grundlage entbehre. C. Das Kassationsgericht des Kantons Zürich wies mit Beschluss vom 21. April 2007 die Nichtigkeitsbeschwerde des Beklagten gegen das Urteil des Handelsgerichts ab, soweit darauf eingetreten werden konnte. Das Kassationsgericht trat zunächst auf die Noven nicht ein; die Rüge, wonach der Antrag auf Anordnung für Schutzmassnahmen in Bezug auf die eingelegten Dokumente zu Unrecht als gegenstandslos geworden erklärt worden sei, verwarf das Kassationsgericht, weil die Dokumente dem Beklagten zurückgegeben wurden, ohne dass der Klägerin Einsicht gewährt worden war. Die Rüge der Gehörsverletzung erachtete das Gericht sodann für verfehlt, weil das Handelsgericht sich mit den Behauptungen auseinandergesetzt hatte, zu denen der Beklagte die Dokumente angerufen hatte. Die Rüge, die Feststellung des Handelsgerichts, wonach keine Situation vorgelegen habe, in welcher Vermittlungsmäkelei üblicherweise eingesetzt werde, sei tatsachenwidrig, verwarf das Gericht mit dem Hinweis, das Handelsgericht sei entgegen der Behauptung des Beklagten durchaus davon ausgegangen, eine Vermittlungsmäkelei sei möglich. Auf die Rüge der Verletzung von Bundesrecht trat das Gericht nicht ein. Der Vorwurf, die Annahme des Handelsgerichts, die Regierung des Landes A._ habe nur einen begrenzten Verhandlungsspielraum gehabt, stehe im Widerspruch zu einem Gutachten, verwarf das Kassationsgericht ebenso wie den Vorwurf der Gehörsverletzung, die angeblich durch die Nichtbeachtung der privatrechtlichen Natur der Ausschreibung begangen worden sei. Die Rüge der Gehörsverweigerung durch angebliche Nichtberücksichtigung eines weiteren Gutachtens verwarf das Gericht in der Erwägung, es stehe darin etwas anderes als vom Beklagten behauptet. Auch die Rüge gegen die Feststellungen, der Entscheid über den Zuschlag sei politischer Natur gewesen bzw. das Handelsgericht habe die Tätigkeit des Beklagten als Handelsförderung qualifiziert, verwarf das Kassationsgericht mit der Begründung, davon sei das Handelsgericht gar nicht ausgegangen. Die Bestreitung, dass der Beklagte seine angebliche Mäklertätigkeit auf Briefpapier des Honorarkonsulates getätigt hatte, wertete das Kassationsgericht als nicht nachvollziehbar, soweit entsprechende Rügen die Feststellung überhaupt zutreffend wiedergaben. Die Verletzung der Gehörsverweigerung in Bezug auf Beweismassnahmen zu einem tatsächlich übereinstimmenden Parteiwillen verwarf das Kassationsgericht, weil der Beklagte keine diesbezüglichen Behauptungen aufgestellt hatte. Schliesslich wies es die Rüge betreffend die Kosten ab. C. Das Kassationsgericht des Kantons Zürich wies mit Beschluss vom 21. April 2007 die Nichtigkeitsbeschwerde des Beklagten gegen das Urteil des Handelsgerichts ab, soweit darauf eingetreten werden konnte. Das Kassationsgericht trat zunächst auf die Noven nicht ein; die Rüge, wonach der Antrag auf Anordnung für Schutzmassnahmen in Bezug auf die eingelegten Dokumente zu Unrecht als gegenstandslos geworden erklärt worden sei, verwarf das Kassationsgericht, weil die Dokumente dem Beklagten zurückgegeben wurden, ohne dass der Klägerin Einsicht gewährt worden war. Die Rüge der Gehörsverletzung erachtete das Gericht sodann für verfehlt, weil das Handelsgericht sich mit den Behauptungen auseinandergesetzt hatte, zu denen der Beklagte die Dokumente angerufen hatte. Die Rüge, die Feststellung des Handelsgerichts, wonach keine Situation vorgelegen habe, in welcher Vermittlungsmäkelei üblicherweise eingesetzt werde, sei tatsachenwidrig, verwarf das Gericht mit dem Hinweis, das Handelsgericht sei entgegen der Behauptung des Beklagten durchaus davon ausgegangen, eine Vermittlungsmäkelei sei möglich. Auf die Rüge der Verletzung von Bundesrecht trat das Gericht nicht ein. Der Vorwurf, die Annahme des Handelsgerichts, die Regierung des Landes A._ habe nur einen begrenzten Verhandlungsspielraum gehabt, stehe im Widerspruch zu einem Gutachten, verwarf das Kassationsgericht ebenso wie den Vorwurf der Gehörsverletzung, die angeblich durch die Nichtbeachtung der privatrechtlichen Natur der Ausschreibung begangen worden sei. Die Rüge der Gehörsverweigerung durch angebliche Nichtberücksichtigung eines weiteren Gutachtens verwarf das Gericht in der Erwägung, es stehe darin etwas anderes als vom Beklagten behauptet. Auch die Rüge gegen die Feststellungen, der Entscheid über den Zuschlag sei politischer Natur gewesen bzw. das Handelsgericht habe die Tätigkeit des Beklagten als Handelsförderung qualifiziert, verwarf das Kassationsgericht mit der Begründung, davon sei das Handelsgericht gar nicht ausgegangen. Die Bestreitung, dass der Beklagte seine angebliche Mäklertätigkeit auf Briefpapier des Honorarkonsulates getätigt hatte, wertete das Kassationsgericht als nicht nachvollziehbar, soweit entsprechende Rügen die Feststellung überhaupt zutreffend wiedergaben. Die Verletzung der Gehörsverweigerung in Bezug auf Beweismassnahmen zu einem tatsächlich übereinstimmenden Parteiwillen verwarf das Kassationsgericht, weil der Beklagte keine diesbezüglichen Behauptungen aufgestellt hatte. Schliesslich wies es die Rüge betreffend die Kosten ab. D. Mit Beschwerde in Zivilsachen vom 30. Mai 2007 stellt der Beschwerdeführer dem Bundesgericht folgende Anträge: 1. Es seien Ziff. 1 des Dispositives des Beschlusses vom 21. April 2007 des Kassationsgerichts des Kantons Zürich (...) und Ziff. 2 des Dispositives des Urteils vom 3. Juli 2006 des Handelsgerichts des Kantons Zürich (...) aufzuheben, und es sei der Prozess im Sinne der bundesgerichtlichen Erwägungen zur Neubeurteilung an das Handelsgericht des Kantons Zürich zurückzuweisen. 2. Eventuell: Es sei Ziff. 1 des Dispositives des Beschlusses vom 21. April 2007 des Kassationsgerichts des Kantons Zürich (...) aufzuheben, und es sei der Prozess im Sinne der bundesgerichtlichen Erwägungen zur Neubeurteilung an das Kassationsgericht des Kantons Zürich zurückzuweisen. 3. In Aufhebung von Ziff. 2-4 des Dispositives des Beschlusses vom 21. April 2007 des Kassationsgerichts des Kantons Zürich (...) und von Ziff. 3-5 des Dispositives des Urteils vom 3. Juli 2006 des Handelsgerichts des Kantons Zürich (...) seien die Gerichtskosten der vorinstanzlichen Verfahren der Beschwerdegegnerin aufzuerlegen. Überdies sei sie zu verpflichten, dem Beschwerdeführer eine angemessene Parteientschädigung für die vorinstanzlichen Verfahren zu entrichten. .. ..." Der Beschwerdeführer rügt, das Handelsgericht und das Kassationsgericht hätten in Bezug auf Dokumente über die Ausgestaltung des Auswahlverfahrens im Land A._ bundesrechtswidrige Erwägungen angestellt, das Kassationsgericht habe ihm das rechtliche Gehör verweigert in Bezug auf die handelsgerichtliche Erwägung, wonach keine klassische Situation vorgelegen habe, in der üblicherweise Vermittlungsmäkler eingesetzt würden, durch die Nichtberücksichtigung der Parteigutachten sei ihm das rechtliche Gehör verweigert worden, das Kassationsgericht habe willkürlich und in Verweigerung des rechtlichen Gehörs die Erwägungen des Handelsgerichts zur Lobbyistentätigkeit nicht beanstandet und bundesrechtswidrige Erwägungen zu seiner Tätigkeit als Honorarkonsul angestellt, willkürlich aus den bei den Akten liegenden Schreiben nicht auf eine Mäklertätigkeit geschlossen und ausserdem sei das Kassationsgericht verfassungswidrig zusammengesetzt gewesen. Der Beschwerdeführer rügt, das Handelsgericht und das Kassationsgericht hätten in Bezug auf Dokumente über die Ausgestaltung des Auswahlverfahrens im Land A._ bundesrechtswidrige Erwägungen angestellt, das Kassationsgericht habe ihm das rechtliche Gehör verweigert in Bezug auf die handelsgerichtliche Erwägung, wonach keine klassische Situation vorgelegen habe, in der üblicherweise Vermittlungsmäkler eingesetzt würden, durch die Nichtberücksichtigung der Parteigutachten sei ihm das rechtliche Gehör verweigert worden, das Kassationsgericht habe willkürlich und in Verweigerung des rechtlichen Gehörs die Erwägungen des Handelsgerichts zur Lobbyistentätigkeit nicht beanstandet und bundesrechtswidrige Erwägungen zu seiner Tätigkeit als Honorarkonsul angestellt, willkürlich aus den bei den Akten liegenden Schreiben nicht auf eine Mäklertätigkeit geschlossen und ausserdem sei das Kassationsgericht verfassungswidrig zusammengesetzt gewesen. E. Die Beschwerdegegnerin beantragt in der Antwort, die Beschwerde gegen das Urteil des Kassationsgerichts sei abzuweisen, soweit darauf einzutreten ist, soweit sie sich gegen das Handelsgericht richte, sei darauf nicht einzutreten, eventuell sei sie abzuweisen. Das Kassationsgericht des Kantons Zürich hält in seiner Stellungnahme fest, der Fall sei in Anwendung von Ziff. II. 3 Abs. 2 des Konstituierungsbeschlusses vom 13. Dezember 2005 (RB 2005 S. 18 ff.) ordentlicherweise der Besetzung 5 zugeteilt worden, wobei der Präsident sowie der Kassationsrichter Donatsch im Ausstand gewesen seien, weshalb der Vizepräsident die Besetzung ergänzt habe. Im Übrigen verzichtet das Gericht auf eine Stellungnahme. Das Kassationsgericht des Kantons Zürich hält in seiner Stellungnahme fest, der Fall sei in Anwendung von Ziff. II. 3 Abs. 2 des Konstituierungsbeschlusses vom 13. Dezember 2005 (RB 2005 S. 18 ff.) ordentlicherweise der Besetzung 5 zugeteilt worden, wobei der Präsident sowie der Kassationsrichter Donatsch im Ausstand gewesen seien, weshalb der Vizepräsident die Besetzung ergänzt habe. Im Übrigen verzichtet das Gericht auf eine Stellungnahme. F. Mit Verfügung vom 29. Juni 2007 gewährte der Präsident der I. zivilrechtlichen Abteilung der Beschwerde antragsgemäss die aufschiebende Wirkung. Auf eine Stellungnahme zur ergänzenden Begründung des Kassationsgerichts hat der Beschwerdeführer verzichtet.