Sachverhalt:
A. Der 1941 geborene S._ bezog seit 1. Januar 1999 Arbeitslosenentschädigung. Mit Verfügung vom 25. Juni 2003 verneinte das Amt für Wirtschaft und Arbeit des Kantons Zürich (nachfolgend AWA) seinen Anspruch auf Arbeitslosenentschädigung ab 17. September 1999, woran es mit Einspracheentscheid vom 14. April 2004 festhielt. Hiegegen erhob S._ Beschwerde beim Sozialversicherungsgericht des Kantons Zürich. Mit Verfügung vom 17. Juli 2004 forderte die Arbeitslosenkasse GBI (nunmehr Unia Arbeitslosenkasse, nachfolgend Kasse) von ihm für den Zeitraum ab September 1999 bis November 2002 zu viel bezahlte Leistungen im Betrag von Fr. 126'467.45 zurück, wogegen er Einsprache erhob. Mit Verfügung vom 17. August 2004 sistierte die Kasse dieses Einspracheverfahren bis zur rechtskräftigen Erledigung des gerichtlichen Verfahrens betreffend den Einspracheentscheid vom 14. April 2004. Im Rahmen dieses Verfahrens entschied das Bundesgericht letztinstanzlich, S._ habe ab 1. Januar 2001 keinen Anspruch auf Arbeitslosenentschädigung (Urteil C 32/06 vom 29. März 2007). Mit Einspracheentscheid vom 14. Mai 2007 hob die Kasse die Verfahrenssistierung auf und wies die Einsprache des Versicherten gegen die Rückforderungsverfügung vom 17. Juli 2004 ab.
B. In teilweiser Gutheissung der hiegegen erhobenen Beschwerde änderte das kantonale Gericht den Einspracheentscheid insoweit ab, als es den von S._ zurückzuerstattenden Betrag auf Fr. 63'397.65 reduzierte. Zur Prüfung der Erlassvoraussetzungen wies es die Sache an die Kasse zurück (Entscheid vom 30. Juni 2009).
C. Mit Beschwerde beantragt S._, der kantonale Entscheid sowie die Rückforderungsverfügung seien aufzuheben und die Rückforderung wegen Verwirkung abzuweisen.
Die Kasse und das Staatssekretariat für Wirtschaft (seco) verzichten auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Immerhin prüft es, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (nicht publ. E. 1.1 des Urteils <ref-ruling>, in SVR 2010 UV Nr. 2 S. 7 [8C_784/2008]). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>) und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Dies ist auf Grund der Vorbringen in der Beschwerde zu prüfen (nicht. publ. E. 1 des Urteils <ref-ruling>, in SVR 2009 IV Nr. 52 S. 161 [8C_763/2008]).
2. Die Rückforderungsverfügung vom 17. Juli 2004 bzw. der sie bestätigende Einspracheentscheid vom 14. Mai 2007 sind nach In-Kraft-Treten des ATSG am 1. Januar 2003 ergangen. Die Rückerstattung betrifft indessen vor diesem Zeitpunkt, nämlich bis November 2002 ausgerichtete Taggelder. Ob unter diesen Umständen <ref-law> oder die bis Ende 2002 geltende Rückerstattungsordnung anwendbar ist, kann offen bleiben, da die nach dem ATSG für die Rückerstattung massgeblichen Grundsätze aus der früheren Regelung und Rechtsprechung hervorgegangen sind (<ref-ruling> E. 5.2 S. 319). Dies betrifft insbesondere die hier umstrittene Verwirkungsfrage (vgl. aArt. 95 Abs. 4 ATSG; Urteil C 54/06 vom 12. September 2006 E 4.1). Nachfolgend werden die einschlägigen Bestimmungen des ATSG zitiert (vgl. auch Urteil M 1/05 vom 29. April 2005 E. 2.2).
Die Vorinstanz hat die Bestimmungen über die Rückforderung unrechtmässig bezogener Leistungen der Arbeitslosenversicherung (<ref-law> in Verbindung mit Art. 25 Abs. 1 und 2 ATSG) zutreffend dargelegt. Darauf wird verwiesen.
3. Unbestritten ist, dass der Rückforderungsbetrag masslich auf Fr. 63'397.65 zu begrenzen ist, da das Bundesgericht im Urteil C 32/06 vom 29. März 2007 die Taggeldberechtigung des Beschwerdeführers erst ab 1. Januar 2001 verneint hat. Nicht streitig ist weiter, dass er die ihm in dieser Höhe ausgerichteten Taggelder zweifellos zu Unrecht bezogen hat und der Rückforderungsbetrag von erheblicher Bedeutung ist (<ref-ruling> E. 1.1; ARV 2000 Nr. 40 S. 208 E. 3b; Urteil 8C_214/2009 vom 1. Oktober 2009 E. 7). Gestützt auf <ref-law> in Verbindung mit <ref-law> ist der Betrag mithin grundsätzlich zurückzuerstatten (vgl. auch Urteil 8C_293/2008 vom 30. Juli 2009 E. 3). Umstritten und zu prüfen ist einzig, ob der Rückforderungsanspruch verwirkt ist.
4. Gemäss <ref-law> verjährt der Rückforderungsanspruch innert eines Jahres, nachdem die Versicherungseinrichtung davon Kenntnis erhalten hat, spätestens aber fünf Jahre nach der Auszahlung der Leistung. Es handelt sich um Verwirkungsfristen (vgl. auch die im Rahmen des ATSG anwendbare Rechtsprechung: <ref-ruling> E. 1 S. 382; SVR 1997 ALV Nr. 84 S. 255 E. 2c/aa).
Gestützt auf die Publizitätswirkung des Handelsregisters (Art. 932 f. OR) ist es der Verwaltung verwehrt einzuwenden, eine Dritten gegenüber wirksam gewordene Eintragung im Handelsregister nicht gekannt zu haben. Ist der Eintrag allein bereits hinreichend klar bezüglich der einen Entschädigungsanspruch ausschliessenden Eigenschaft des Leistungsansprechers, beginnt die Verwirkungsfrist von Anfang an, d.h. mit der ersten Auszahlung der Taggelder, zu laufen. Eines zweiten Anlasses für den Beginn der einjährigen relativen Verwirkungsfrist gemäss <ref-law> bedarf es diesfalls nicht (<ref-ruling> E. 5b/aa S. 275). Gibt der Eintrag hingegen erst - aber immerhin - Anhaltspunkte, die einer weiteren Abklärung bedürfen, so zum Beispiel allenfalls beim Geschäftsführer einer GmbH ohne Gesellschaftereigenschaft, so ist der Beginn der Verwirkungsfrist bei Säumnis auf den Zeitpunkt festzusetzen, in welchem die Verwaltung mit zumutbarem Einsatz ihre unvollständige Kenntnis so zu ergänzen im Stande gewesen wäre, dass der Rückforderungsanspruch hätte geltend gemacht werden können (nicht publ. E. 5.1 des Urteils <ref-ruling>, in: SVR 2008 KV Nr. 4 S. 11 [K 70/06]; SVR 2004 AlV Nr. 5 S. 13 [C 17/03]; ARV 2009 S. 346 E. 4.1 [8C_293/2008]; vgl. die Weisung des seco 008-AVIG-Praxis 2010/1). Ist für die Leistungsfestsetzung das Zusammenwirken mehrerer Behörden notwendig, genügt es, dass die erforderliche Kenntnis bei einer der zuständigen Verwaltungsstellen vorhanden ist (<ref-ruling> E. 3a S. 433; SVR 2004 IV Nr. 41 S. 131 E. 4.2 [I 62/02]).
5. Die Vorinstanz hat erwogen, das AWA habe mit Verfügung vom 25. Juni 2003 bzw. Einspracheentscheid vom 14. April 2004 entschieden, der Versicherte besitze ab 17. September 1999 keinen Anspruch auf Arbeitslosenentschädigung. Im Rahmen der nachfolgenden Gerichtsverfahren habe das Bundesgericht mit Urteil C 32/06 diesen Anspruch ab 1. Januar 2001 verneint. Der Rückerstattungsanspruch der Kasse könne erst nach rechtskräftiger Erledigung der Anspruchsfrage bestehen, weshalb die einjährige Verwirkungsfrist frühestens am 29. März 2007 zu laufen begonnen habe. Deshalb könne nicht von verspäteter Rückforderung ausgegangen werden.
Der Beschwerdeführer wendet ein, das AWA habe spätestens bei Erlass der Verfügung vom 25. Juni 2003 in grundsätzlicher und masslicher Hinsicht die erforderliche Kenntnis vom Rückforderungsanspruch gehabt. Diese Kenntnis müsse sich die Kasse anrechnen lassen. Demnach sei ihre Rückforderungsverfügung vom 17. Juli 2004 verspätet gewesen. Die Vorinstanz habe Bundesrecht verletzt, indem sie für den Beginn der relativen einjährigen Verwirkungsfrist auf die letztinstanzliche Erledigung der gerichtlichen Auseinandersetzung betreffend Vermittlungsfähigkeit des Beschwerdeführers abgestellt habe.
6. 6.1 Das Bundesgericht legte im den Beschwerdeführer betreffenden Urteil C 32/06 (vgl. auch E. 3 hievor) dar, seine Ehefrau sei seit 27. Juli 1998 und auch ab 1. Januar 2001 Verwaltungsratspräsidentin der Firma M._ gewesen, womit ihr eine arbeitgeberähnliche Stellung zugekommen sei (<ref-law>). Der Beschwerdeführer habe die Beitragszeit bezüglich der zweiten Rahmenfrist für den Leistungsbezug (1. Januar 2001 bis 31. Dezember 2002) nur aufgrund der Zwischenverdiensttätigkeit in dieser Firma erfüllen können. Seine Ehefrau hätte keine Leistungen der Arbeitslosenversicherung beziehen können, weshalb ihm als mitarbeitendem Ehemann gemäss <ref-law> ein Anspruch auf Arbeitslosenentschädigung ab 1. Januar 2001 ebenfalls verwehrt bleibe.
6.2 Nach dem Gesagten ergibt sich der Sachverhalt, der zur Unrechtmässigkeit der Leistungsausrichtung an den Beschwerdeführer führte, ohne Weiteres aus dem Handelsregister (seine Ehefrau war Verwaltungsratspräsidentin der Firma M._). Unter diesen Umständen begann die einjährige Verwirkungsfrist gemäss <ref-law> mit der Auszahlung der Taggelder zu laufen (siehe E. 4 hievor). Da die letzten streitigen Taggelder im November 2002 ausbezahlt worden waren, war die Rückforderungsverfügung der Kasse vom 17. Juli 2004 verspätet und ihr Rückforderungsanspruch damit verwirkt, zumal die Stellung der Ehefrau des Beschwerdeführers als Verwaltungsratspräsidentin in obiger Firma keiner weiteren Abklärungen bedurfte (vgl. auch <ref-ruling> E. 5b S. 275 f.).
Eine Verletzung des Rechtsmissbrauchsverbots durch den Versicherten ist nicht ersichtlich (vgl. ARV 2009 S. 346 E. 4.6.2).
6.3 Es kann nicht davon ausgegangen werden, die bloss leistungsverneinende Verfügung des AWA vom 25. Juni 2003 sei fristwahrend gewesen. Denn abgesehen davon, dass darin keine Rückforderung geltend gemacht wurde (vgl. BGE 135 V 579 E. 4.3.1 S. 583 f.), wäre das AWA diesbezüglich gar nicht zuständig gewesen. Die Rückforderung war vorliegend vielmehr Aufgabe der Kasse (vgl. Art. 81, Art. 83a Abs. 3, Art. 85 AVIG; Botschaft zu einem revidierten Arbeitslosenversicherungsgesetz vom 28. Februar 2001, BBl 2001 2245, 2296; THOMAS NUSSBAUMER, Arbeitslosenversicherung, in: Ulrich Meyer [Hrsg.], Schweizerisches Bundesverwaltungsrecht [SBVR], Soziale Sicherheit, 2. Aufl., S. 2456 Rz. 913).
7. Die Gerichtskosten werden der unterliegenden Beschwerdegegnerin auferlegt (<ref-law>; <ref-ruling>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 30. Juni 2009 aufgehoben.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Sozialversicherungsgericht des Kantons Zürich zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Staatssekretariat für Wirtschaft schriftlich mitgeteilt.
Luzern, 10. Februar 2010
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Jancar