Sachverhalt: A.a Die S._ AG (S._; heute im Konkurs) war eine auf Informatikdienstleistungen spezialisierte Gesellschaft und seit Dezember 1999 eine vollkonsolidierte 100 %ige Tochtergesellschaft der F._-Bank AG (Beschwerdegegnerin). Im Jahre 1995 hatte die G._-Bank ihre gesamte Applikationsentwicklung mit ca. 350 IT-Spezialisten in die damals von ihr zu 100 % beherrschte S._ ausgegliedert, was für diese eine Verdoppelung ihres Mitarbeiterbestands zur Folge hatte. Um den Konzernbedürfnissen der G._-Bank zu genügen, wurde die S._ in der Folge strategisch auf die Erbringung von IT-Dienstleistungen für Banken und Versicherungen ausgerichtet. Nach der Fusion der H._-Bank und der G._-Bank zur F._-Bank Ende 1997 wurde entschieden, dass künftig die von der H._-Bank entwickelte IT-Plattform (M._) und nicht diejenige der G._-Bank genutzt werden sollte. Für die fortgesetzte Wartung der G._-Bank-Plattform und die Überführung zahlreicher vorzugswürdiger G._-Bank-Applikationen ins M._-System war jedoch weiterhin S._ Know-how und Personal gefragt. Daneben wurden S._-Mitarbeiter zur Befriedigung des weiteren F._-Bank IT-Dienstleistungsbedarfs beigezogen. Allerdings geschah dies weniger auf dem Weg eines Einkaufs von Lösungen auf der Basis werkvertraglicher Abreden als durch temporäre Überlassung von Arbeitskräften nach dem Modell eines Personalverleihs. Die S._ wurde dadurch zu einer Art ausgelagerter F._-Bank IT-Abteilung. A.b Anfangs 2000 übernahm die S._ die in Köln ansässige V._-Gruppe Unternehmensgruppe, ein EDV-Beratungsunternehmen mit Schwerpunkt in der EDV-Beratertätigkeit bei Banken. Finanziert wurde diese Akquisition durch ein von der A._-Bank (Beschwerdeführerin 1) angeführtes Bankenkonsortium (Beschwerdeführerinnen). Zum Zweck dieser Übernahme wurde als Kreditnehmerin zwischen die S._ und die V._-Gruppe Unternehmensgruppe eine S._ (Deutschland) GmbH (S._-D) dazwischengeschaltet. Im Rahmen der Finanzierung der Akquisition der V._-Gruppe schlossen die Beschwerdeführerin 1 und die S._-D (damals noch als W._ GmbH firmierend) als Kreditnehmerin am 28. Januar 2000 eine Kreditvereinbarung, auf deren Grundlage die Beschwerdeführerin 1 der S._-D ein Darlehen in der Höhe von DEM 160 Mio. sowie eine Revolving Credit Facility ("RCF") von DEM 10 Mio. zur Verfügung stellte. Mit Kreditversicherungsvertrag vom gleichen Tag garantierte die S._ der Beschwerdeführerin 1 zur Sicherung des Kredites an die S._-D einen Betrag bis max. DEM 170 Mio. Am 28. Februar 2000 wurde eine weitere Kreditvereinbarung über eine RCF von DEM 15 Mio. geschlossen. Die beiden RCF wurden mit Änderungsvertrag vom 20. Dezember 2001 aufgehoben. A.c Durch Verkaufs- und Abtretungsverträge vom 10. August 2000 und 26. September 2000 syndizierte die Beschwerdeführerin 1 als Konsortialführerin die auf der Grundlage der Kreditvereinbarungen vom 28. Januar 2000 und 28. Februar 2000 zur Verfügung gestellten Kreditmittel an die Mitglieder des Bankenkonsortiums. Durch die Syndizierung wurden die Mitglieder des Bankenkonsortiums Gläubiger der S._ (richtig: S._-D). Hinsichtlich der gestellten Sicherheiten wurde ein Sicherheitenpool mit den übrigen Konsorten gebildet; am 10. August 2000 wurde zu diesem Zweck ein Sicherheitenpoolvertrag zwischen den Mitgliedern des Bankenkonsortiums geschlossen. A.d Im Rahmen einer Restrukturierungsvereinbarung vom 20. Dezember 2001 verständigten sich das Bankenkonsortium und die Beschwerdegegnerin darauf, zum einen den Liquiditätsbedarf des Kreditnehmers (S._-D) sowie der S._, die einzige Gesellschafterin des Kreditnehmers war, zu sichern und zum anderen eine drohende Überschuldung zu verhindern. Die Leistungen des Bankenkonsortiums bestanden u. a. in der Aussetzung der "Financial Covenants" der Kreditvereinbarung vom 28. Januar 2000 mit Verzicht auf das Kündigungsrecht bis zum 31. Dezember 2002, der Aussetzung der Tilgung bis zum 31. Dezember 2003, der Stundung eines Zinsanteils, der Bereitschaft zu einem Rangrücktritt im Betrag von EUR 15.35 Mio. (unter bestimmten Voraussetzungen) und der Einräumung einer neuen working-capital-facility im Betrag von EUR 7.65 Mio. Die Bedingungen der Kreditverträge wurden geändert; die Beschwerdegegnerin verpflichtete sich, im Rahmen der Restrukturierung, weitere Kreditmittel als Darlehen zur Verfügung zu stellen und diverse bestehende Forderungen zu subordinieren. Die Beschwerdegegnerin wurde Partei des Sicherheitenpoolvertrages vom 10. August 2000 in einer geänderten Fassung; mit Vertragsänderung vom 20. Dezember 2001 wurde dies perfekt. Mit Pfandvertrag und Verpfändungserklärung vom 25. April 2002 / 8. Mai 2002 zwischen den Sicherheitenpoolbanken einerseits und der S._ andererseits wurden die von der S._ gehaltenen Aktien an der S._ Business Services AG gemäss Restrukturierungsvereinbarung als Sicherheit für die gegenüber der S._-D gewährten Darlehen verpfändet. Als weitere Sicherheiten für die gewährten Darlehen schlossen die Beschwerdeführerin 1 als Vertreterin der am Sicherheitenpoolvertrag beteiligten Banken und die S._ mit Verträgen vom 25. April 2002 / 8. Mai 2002 eine Globalabtretung sowie eine Sicherungsübereignung des gesamten Anlagevermögens ab. A.e Am 15. November 2002 erklärte die Beschwerdeführerin 1 im Namen der Sicherheitenpoolbanken die Inanspruchnahme der Garantie der S._ bis max. DEM 170 Mio. in einem Betrag von EUR 75'812'220.-- und am 3. März 2003 für weitere EUR 11'107'309.10. Bereits mit Kreditversicherungsvertrag vom 25. April 2002 hatte die S._ der Beschwerdeführerin 1 zur Sicherung der der S._-D zur Verfügung gestellten Kredite (zusätzlich) einen Betrag von max. EUR 48'045'120.-- garantiert. Die Inanspruchnahme dieses Betrages erklärte die Beschwerdeführerin 1 am 27. Februar 2003. Auf Antrag der S._ bewilligte der Nachlassrichter des Bezirksgerichts Zürich am 9. Dezember 2002 die provisorische Nachlassstundung. Mit Verfügung vom 10. Februar 2003 wurde der S._ die definitive Nachlassstundung bis zum 5. August 2003 gewährt und die X._ AG Zürich als Sachwalterin bestellt. Mit Verfügung des Nachlassrichters vom 26. September 2003 wurde der vorgeschlagene Nachlassvertrag nicht bestätigt und die definitive Nachlassstundung für beendet erklärt. Mit Verfügung des Konkursrichters des Bezirksgerichts Zürich vom 3. November 2003 wurde schliesslich der Konkurs über die S._ eröffnet. Die Beschwerdeführerinnen gaben im Konkursverfahren eine Hauptforderung von EUR 75'663'663.25 bzw. CHF 111'301'248.64 ein. Die Konkursverwaltung und die übrigen Gläubiger liessen diese Forderungen formell zu. In einem Vergleich zwischen dem Bankenkonsortium und der Konkursverwaltung vom 9. März 2005 sagte das Bankenkonsortium zu, seine Hauptforderung um CHF 14 Mio. zu reduzieren und auf (weitere) Forderungen von CHF 9.31 Mio. und CHF 57'355.-- ganz zu verzichten. Das Bankenkonsortium hat im Konkurs der S._ demzufolge noch formell zugelassene Ausstände von insgesamt CHF 97'301'248.64 (CHF 111'301'248.64 ./. CHF 14 Mio.). Auch die S._-D befindet sich in Deutschland in einem Insolvenzverfahren. B. Die Beschwerdeführerinnen beantragten dem Handelsgericht des Kantons Zürich mit Klage vom 8. November 2006, die Beschwerdegegnerin sei zu verpflichten, ihnen den Betrag von Fr. 97'301'248.64 nebst Zins zu 5 % seit dem 7. Dezember 2002 zu bezahlen. Sie stützten ihre Forderung auf eine Haftung der Beschwerdegegnerin aus erwecktem und enttäuschtem Vertrauen, aus positiver Vertragsverletzung und aus aktienrechtlicher Verantwortlichkeit. Das Handelsgericht wies die Klage mit Urteil vom 12. Mai 2009 ab. C. Gegen diesen Entscheid erhoben die Beschwerdeführerinnen Beschwerde in Zivilsachen. Sie verlangen die Gutheissung ihrer Klage. Eventuell sei die Sache zu neuer Beurteilung an das Handelsgericht zurückzuweisen. Die Vorinstanz hat auf eine Vernehmlassung zur Beschwerde verzichtet. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde. Mit Präsidialverfügung vom 3. Juli 2009 wurde ein Gesuch der Beschwerdeführerinnen, es sei der Beschwerde die aufschiebende Wirkung zu gewähren, abgewiesen.