Sachverhalt: A. Die Y. Z._ AG schloss am 3. Mai 1985 als Franchisegeberin mit der X._ mit beschränkter Haftung mit Sitz in K._ (Beschwerdeführerin) ein Franchise-Agreement, das eine ordentliche Vertragsdauer von 99 Jahren vorsah. Dieses löste einen vorangegangenen Vertrag zwischen der Y. Z._ AG einerseits und einer Dritten sowie der Beschwerdeführerin andererseits aus dem Jahre 1978 ab. Am 1. April 1994 übernahm die Y. Z. Q._ SA mit Sitz in L._ (Beschwerdegegnerin) die Aktiven und Passiven der Y. Z._ AG. Im Rahmen der vertraglichen Zusammenarbeit sind die Beschwerdeführerin und die Beschwerdegegnerin kommerzielle Anbieter von Unternehmens- und Produkteinformationen für geschäftliche Interessenten im Industrie-, Handels- und Dienstleistungsbereich, wobei die von ihnen zur Verfügung gestellten Daten dadurch gekennzeichnet sind, dass sie nach dem sogenannten "Y._"-System klassifiziert und gekennzeichnet sind. Die so aufbereiteten Daten enthalten namentlich Business-to-Business Informationen und umfassen in der Regel ganze Unternehmensprofile. Ursprüngliches und immer noch genutztes Medium für den Vertrieb der erhobenen Unternehmensinformationen ist das "Y._"-Verzeichnis in Buchform. Im Laufe der Zeit sind sowohl eine Version auf CD-Rom als auch eine Online-Anwendung mittels der Internet-Plattform "www.Y._.com" hinzugekommen. Das "Y._"-Geschäft beruht im Wesentlichen auf einem Netz aus lokalen Datenbanken, in denen die Informationen von den jeweiligen Franchisenehmern erhoben, erfasst und einheitlich klassifiziert werden und die über das "Y._"-Franchisenetz automatisch mit einem weltweiten Datennetzwerk verbunden sind. Im Franchise-Agreement wurde der Beschwerdeführerin das Recht eingeräumt, während der Vertragsdauer das "Y._"-System im Vertragsgebiet M._ exklusiv anzubieten und zu vermarkten, unter exklusiver Nutzung des "Y._"-Klassifikationssystems, der Bezeichnung "Y._" sowie der "Y._"-Marke der Beschwerdegegnerin. Auf der anderen Seite war die Beschwerdeführerin u.a. verpflichtet, den Verkauf der "Y._"-Verzeichnisse in ihrem Vertragsgebiet nach Kräften, wie auch den Verkauf der "Y._"-Verzeichnisse anderer Franchisenehmer (in verschiedenen Ländern) zu fördern und alles Mögliche zu unternehmen, um ein Maximum an bezahlten Einträgen in den "Y._"-Verzeichnissen zu erreichen. Die Beschwerdeführerin schuldete der Franchisegeberin sodann - neben einmaligen, jeweils separat vereinbarten Pauschalgebühren - periodisch wiederkehrende Gebühren. Zum einen musste sie der Beschwerdegegnerin jährlich eine vom Bruttoumsatz abhängige Franchise-Fee abführen, gemäss Zusatzvereinbarung vom 15. Juli 1996 auch vom Umsatz aus der elektronischen Vermarktung des "Y._"-Systems. Zum anderen musste die Beschwerdeführerin nach einer weiteren Vereinbarung vom 17. November 2000 sogenannte "Internet-Fees" entrichten, die auf der Basis des aus der Vermarktung der Internetplattform "www.Y._.com" erzielten Umsatzes bemessen wurden. Bei der Data Sharing Fee bestand dabei die Besonderheit, dass diese anschliessend nach einem bestimmten Verteilungsschlüssel wieder an alle Franchisenehmer ausbezahlt wurde. In jedem Fall schuldete die Beschwerdeführerin eine umsatzunabhängige Minimalfranchisegebühr, die zuletzt Fr. 60'000.-- im Jahr ausmachte. Am 5. April 2004 stellte die Beschwerdegegnerin der Beschwerdeführerin eine "Notice of default" zu. Sie warf der Beschwerdeführerin die Verletzung verschiedener vertraglicher Pflichten vor, insbesondere der Absatzförderungspflicht einschliesslich der Pflicht, möglichst viele zahlungspflichtige Kundeneinträge in die "Y._"-Verzeichnisse zu erlangen, sowie eine Verletzung der sogenannten Systembefolgungspflicht, und setzte eine Frist von 30 Tagen, um die Vertragsverletzungen zu beheben. Die Beschwerdeführerin wies die Vorwürfe durch ein Schreiben der N._ Rechtsanwälte vom 3. Mai 2004 zurück. Daraufhin kündigte die Beschwerdegegnerin den Franchisevertrag am 17. Mai 2004 mit sofortiger Wirkung. B. Am 6. Juli 2004 machte die Beschwerdegegnerin gegen die Beschwerdeführerin eine Klage vor dem Handelsgericht des Kantons Zürich anhängig. Sie beantragte mit in der Replik modifiziertem Rechtsbegehren u.a., die Beschwerdeführerin sei zu verpflichten, ihr EUR 4'400'000.-- zu zahlen, unter Vorbehalt von Nachforderungen (Klagebegehren Ziff. 2). Die Beschwerdeführerin erhob Widerklage und verlangte mit in der Widerklagereplik modifiziertem Rechtsbegehren u.a., die Beschwerdegegnerin sei zu verpflichten, ihr EUR 40'662'231.-- und CHF 717'979.-- zu bezahlen, zuzüglich Zins von 5 % ab 1. Juli 2004, unter Nachklagevorbehalt (Widerklagebegehren Ziff. 2). Mit Urteil vom 22. November 2007 entschied das Handelsgericht über die entsprechenden Schadenersatzansprüche, indem es das Widerklagebegehren der Beschwerdeführerin abwies und diese in teilweiser Gutheissung des genannten Klagebegehrens Ziff. 2 verpflichtete, der Beschwerdegegnerin EUR 65'000.-- zu bezahlen. Auf Nichtigkeitsbeschwerde der Beschwerdeführerin hin hob das Kassationsgericht des Kantons Zürich diesen Entscheid auf und wies die Sache insoweit zur neuen Entscheidung an das Handelsgericht zurück. Verschiedene weitere Rechtsbegehren der Beschwerdegegnerin wurden vom Handelsgericht mit Beschluss vom 22. November 2007 durch Nichteintreten oder durch Abschreibung zufolge Gegenstandslosigkeit erledigt bzw. mit dem vorstehend genannten Urteil vom gleichen Tag teilweise abgewiesen und teilweise gutgeheissen. Ferner wurde im gleichen Urteil ein weiteres Widerklagebegehren der Beschwerdeführerin abgewiesen. Hinsichtlich dieser weiteren Rechtsbegehren erwuchsen der Beschluss und das Urteil vom 22. November 2007 mangels Anfechtung in Rechtskraft. Mit Urteil vom 25. Januar 2011 entschied das Handelsgericht erneut über die noch hängigen Schadenersatzbegehren (Klagebegehren Ziff. 2 und Widerklagebegehren Ziff. 2), indem es die Beschwerdeführerin erneut verpflichtete, der Beschwerdegegnerin EUR 65'000.-- zu bezahlen, und die Schadenersatzforderung der Beschwerdeführerin erneut abwies. Es befand, der Beschwerdeführerin seien Vertragsverletzungen vorzuwerfen, welche die Beschwerdegegnerin zur vorzeitigen Auflösung des Franchise-Agreements berechtigt hätten. C. Die Beschwerdeführerin beantragt mit Beschwerde in Zivilsachen, dieses Urteil aufzuheben, die Klage der Beschwerdegegnerin vollumfänglich (gemeint wohl: im vor der Vorinstanz noch strittigen Umfang) abzuweisen und die Beschwerdegegnerin in (teilweiser) Gutheissung der Widerklage zu verpflichten, ihr EUR 40'662'231.-- und CHF 717'979.--, nebst Zins, zu bezahlen, unter Vorbehalt der Nachklage. Eventuell sei die Sache zur Neubeurteilung an das Handelsgericht zurückzuweisen. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Handelsgericht verzichtete auf eine Vernehmlassung zur Beschwerde. Ein Gesuch der Beschwerdegegnerin, die Beschwerdeführerin sei zu verpflichten, eine allfällige Parteientschädigung für das bundesgerichtliche Verfahren sicherzustellen, wies die Präsidentin der I. zivilrechtlichen Abteilung mit Verfügung vom 21. März 2011 ab. Am 22. März 2001 wurde der Beschwerde in Bezug auf die Dispositivziffern 1 und 5 des angefochtenen Urteils (Pflicht zur Zahlung von Schadenersatz und einer Prozessentschädigung an die Beschwerdegegnerin) die aufschiebende Wirkung gewährt. 