Sachverhalt: A. A.a Die Stiftung Y._ in Liquidation (Beschwerdegegnerin) ist eine Stiftung mit Sitz in Z._, welche die Verwirklichung der beruflichen Vorsorge im Sinne des Bundesgesetzes über die berufliche Alters-, Hinterlassenen- und Invalidenvorsorge (BVG; SR 831.40) bezweckte. Mit Verfügung des Bundesamts für Sozialversicherungen vom 16. Januar 1996 ist die Stiftung aufgehoben und ihre Liquidation sowie Löschung im Register für berufliche Vorsorge angeordnet worden. Die Liquidation ist gegenwärtig noch im Gange. Die X._ (Beschwerdeführerin) ist eine Aktiengesellschaft mit Sitz in Q._, welche den Betrieb jeder Art von Lebens- und Rentenversicherung (inkl. Unfall-, Kranken- und Invaliditäts-Zusatzversicherung), der selbständigen Kranken- und Invaliditätsversicherung sowie der Rückversicherung in diesen Zweigen bezweckt. A.b Die Beschwerdegegnerin schloss in den Jahren vor 1996 mit den Vorsorgewerken von 11 Arbeitgebern Anschlussvereinbarungen zwecks Verwirklichung der beruflichen Vorsorge im Sinne des BVG. Darin verpflichtete sich die Beschwerdegegnerin, mit der Beschwerdeführerin die notwendigen Versicherungen abzuschliessen. In Erfüllung dieser Pflicht schloss sie in der Folge als Versicherungsnehmerin mit der Beschwerdeführerin 13 Kollektivlebensversicherungsverträge. Nachdem die Beschwerdegegnerin im Januar 1996 aufgehoben wurde, sahen sich die ihr angeschlossenen Vorsorgewerke gezwungen, die Anschlussvereinbarungen mit der Beschwerdegegnerin aufzulösen und sich per 1. Februar 1996 einem neuen Vorsorgeträger anzuschliessen. Damit wurden gleichzeitig auch die Kollektivlebensversicherungsverträge zwischen den Parteien mit Wirkung per 31. Januar 1996 aufgelöst. Im Mai 1996 forderte die Beschwerdegegnerin die Vorsorgewerke dazu auf, Prämienrückstände auszugleichen durch Zahlung an die Beschwerdeführerin, welche auch bisher das Inkasso besorgt hatte. Im August 1996 erstellte die Beschwerdeführerin zuhanden der Vorsorgewerke Abrechnungen. Von September 1996 bis April 1997 zahlten die Vorsorgewerke die Prämienausstände an die Beschwerdeführerin in der Folge grösstenteils. Im November 1996 leistete die Beschwerdeführerin gestützt auf ihre Abrechnungen vom August 1996 Zahlungen an die Beschwerdegegnerin und an die Stiftung R._ der X._ (Stiftung S._), der sich in der Zwischenzeit die meisten Vorsorgewerke angeschlossen haben. Mit Schreiben vom 29. August 1997 wies die Beschwerdegegnerin die Beschwerdeführerin an, die im November 1996 unrechtmässig zurückbehaltenen Auflösungswerte (Deckungskapital) an die Stiftung S._ zu überweisen. Im September 1998 wiederum verlangte die Beschwerdegegnerin von den Vorsorgewerken die Begleichung der ihr gegenüber bestehenden Prämienausstände zwecks Weiterleitung an die neue Vorsorgeeinrichtung. Zwischen November 1999 und April 2000 erstellte die Beschwerdegegnerin provisorische Schlussabrechnungen zuhanden der Vorsorgewerke und nahm auch Überweisungen an die neuen Vorsorgeeinrichtungen vor. A.c In der Folge entzündete sich zwischen den Parteien ein Streit über ausstehende Ansprüche aus den per 31. Januar 1996 aufgelösten Kollektivlebensversicherungsverträgen. Die Beschwerdegegnerin machte geltend, die Beschwerdeführerin habe ihr den Rückkaufswert bei Auflösung der Verträge zu erstatten. Diesen Wert habe die Beschwerdegegnerin mit Abrechnung vom 26. August 1996 berechnet. Die Beschwerdeführerin habe aber vom Anspruch der Beschwerdegegnerin die zum Zeitpunkt der Abrechnung ausstehenden Prämien in Abzug gebracht. In diesem Umfang sei die Beklagte ihren Pflichten aus den Kollektivlebensversicherungsverträgen nicht nachgekommen. Die nachträglich bei der Beschwerdeführerin eingegangenen Prämienzahlungen stünden damit nicht dieser zu, sondern der Beschwerdegegnerin. In Erfüllung der Pflicht zur Erstattung der Rückkaufswerte sei die Beschwerdeführerin daher zur Bezahlung der nachträglich eingegangenen Prämien im Betrag von Fr. 787'470.20 zuzüglich Zins an die Beschwerdegegnerin verpflichtet. B. B.a Am 21. Februar 2005 reichte die Beschwerdegegnerin beim Handelsgericht des Kantons Zürich gegen die Beschwerdeführerin Klage ein mit u.a. den folgenden Anträgen: "1. Es sei die Beklagte aus nach dem 31. Januar 1996 für Rechnung der Kollektivlebensversicherungsverträge gemäss Rechtsbegehren Nr. 2 bei ihr eingegangenen Prämienzahlungen zur Zahlung von CHF 787'470.20, Zins zu 5% seit wann rechtens sowie Betreibungskosten in Höhe von CHF 410.-- an die Klägerin zu verpflichten. Es sei vorzumerken, dass die Geltendmachung weiterer Ansprüche aus den Kollektivlebensversicherungsverträgen gemäss Rechtsbegehren Nr. 2 vorbehalten bleibt. 2. Es sei die Beklagte unter Strafandrohung nach Art. 292 StGB anzuweisen, der Klägerin Auskunft zu erteilen und zu belegen, wann bei ihr die ausstehenden Prämienzahlungen per 31. Januar 1996 der nachfolgenden Vorsorgewerke eingegangen sind: [Liste von Vorsorgewerken] Es sei der Klägerin nach Eingang der Auskunft gemäss Rechtsbegehren Nr. 2 Gelegenheit zu geben, ihren Zinsanspruch gemäss Rechtsbegehren Nr. 1 zu konkretisieren." In der Replikschrift vom 26. Februar 2007 formulierte die Beschwerdegegnerin ihr Rechtsbegehren sodann wie folgt: "1. Es sei die Beklagte zu verpflichten, der Klägerin CHF 787'880.20 zu bezahlen sowie Verzugszins zu 5% auf CHF 2'865.95 seit 12.04.1997, CHF 8'106.30 seit 08.01.1997, CHF 7'090.40 seit 12.04.1997, CHF 5'550.80 seit 08.01.1997, CHF 1'167.20 seit 25.06.1997, CHF 1'552.30 seit 20.02.1997, CHF 675'193.95 seit 30.11.1996, CHF 16'326.25 seit 01.11.1996, CHF 3'320.30 seit 08.01.1997, CHF 1'730.00 seit 25.06.1997, CHF 5'445.80 seit 13.09.1996, CHF 1'659.95 seit 07.09.1996, CHF 303.95 seit 04.10.1996, CHF 430.85 seit 12.04.1997, CHF 23'325.45 seit 12.04.1997, CHF 22'317.60 seit 12.04.1997, CHF 1'446.70 seit 02.09.1999. Es sei vorzumerken, dass die Geltendmachung weiterer Ansprüche aus den Kollektivlebensversicherungsverträgen gemäss Rechtsbegehren Nr. 2 der Klage vom 21. Februar 2005 erhalten bleibt." Mit Urteil vom 29. März 2011 hiess das Handelsgericht die Klage teilweise gut und verurteilte die Beschwerdeführer zur Zahlung eines Betrags von Fr. 777'991.70 (inkl. Betreibungskosten von Fr. 410.--) sowie Zins zu 5% auf den von der Beschwerdegegnerin im reformulierten Rechtsbegehren bezifferten Beträgen. Das Handelsgericht kam zusammenfassend zum Schluss, dass die Beschwerdegegnerin gegenüber der Beschwerdeführerin einen Anspruch auf die zu Rückkaufswerten gewordenen nachträglichen Prämieneingänge hat und die Beschwerdeführerin den Beweis für ihre Behauptung, dass sie die entsprechenden Beträge bereits an die Beschwerdegegnerin überwiesen habe, nicht erbringen konnte. Die Beschwerdeführerin schulde daher die Erfüllung der Rückkaufsforderung im Umfang der Prämieneingänge nach wie vor. C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin dem Bundesgericht, es sei das Urteil des Handelsgerichts aufzuheben und die Klage der Beschwerdegegnerin abzuweisen, eventualiter sei die Streitsache an die Vorinstanz zur Neubeurteilung zurückzuweisen. Gleichzeitig ersucht die Beschwerdeführerin um die Erteilung der aufschiebenden Wirkung. Die Beschwerdegegnerin beantragt in ihrer Vernehmlassung die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. Mit Präsidialverfügung vom 15. Juni 2011 wurde der Beschwerde die aufschiebende Wirkung erteilt.