Sachverhalt:
A. A.a X._ Ltd., (Beschwerdeführerin 1) ist seit Juli 1999 Alleinaktionärin der Y._ Ltd., (Beschwerdeführerin 2; gemeinsam: Beschwerdeführerinnen). Letztere baut in ihren Minen in Südafrika Flussspat (Calciumfluorid) ab.
Z._ Inc. (Beschwerdegegnerin) ist ein internationaler Mischkonzern mit Sitz in den Vereinigten Staaten. Sie ist unter anderem ein bedeutender Produzent von Fluorwasserstoffsäure und benötigt dazu regelmässig grössere Mengen an Flussspat.
A.b Mit Vereinbarung vom 16. Februar 2001 haben sich die Beschwerdeführerinnen verpflichtet, der Beschwerdegegnerin jährlich 85'000 WMT (wet metric tons) Flussspat zu liefern.
Die Parteien vereinbarten für das Jahr 2001 einen Basispreis von USD 106.25 pro DMT (dry metric ton). Für die folgenden Jahre waren die Preise jeweils anhand einer vertraglich festgelegten Formel zu bestimmen, die auf die sogenannten FCA (Free carrier) Preise abstellte, welche die Beschwerdegegnerin anderen Lieferanten zahlte. Für den Fall, dass der anhand dieser Formel berechnete Preis unter einem definierten Mindestpreis oder über einem festgelegten Höchstpreis liegen sollte, sah die Vereinbarung eine Verpflichtung der Parteien vor, in guten Treuen einen Preis auszuhandeln, der für beide fair und angemessen ist.
Die Vereinbarung wurde vorerst bis 31. Dezember 2005 abgeschlossen. Danach sollte der Vertrag jeweils um ein Jahr verlängert werden, sofern er von keiner Partei sechs Monate im Voraus gekündigt wurde. Hinsichtlich der Kündigungsmöglichkeit sieht Ziffer 3(c) unter anderem folgendes vor:
"This Agreement may be terminated by either party in the following instances: (i) if either party is in material breach of the Agreement, which breach remains uncured following thirty (30) days written notice from the non-breaching party, the non-breaching party may terminate the Agreement immediately, by written notice; ..."
Die Vereinbarung enthält neben einer Schiedsklausel eine Rechtswahl zugunsten des schweizerischen Rechts mit folgendem Wortlaut:
"[t]his Agreement shall be construed and interpreted in accordance with the laws of Switzerland as applied between domestic parties provided, however, that the express agreements, understandings and provisions contained herein shall always prevail."
A.c Am 19. Januar 2006 kündigten die Beschwerdeführerinnen die Vereinbarung vom 16. Februar 2001 fristlos mit der Begründung, die Beschwerdegegnerin habe eine wesentliche Vertragsverletzung ("material breach") begangen, indem sie sich geweigert habe, ihre Rechnungen für zwei Lieferungen vollständig zu bezahlen und den Beschwerdeführerinnen die FCA Preise offenzulegen.
Die Beschwerdegegnerin bestritt die Berechtigung der Beschwerdeführerinnen zur Vertragsauflösung und machte gestützt auf verletzte Lieferpflichten Schadenersatzansprüche geltend.
B. B.a Die Beschwerdegegnerin erhob am 15. Februar 2006 Schiedsklage gegen die Beschwerdeführerinnen, im Wesentlichen mit den (im Laufe des Verfahrens abgeänderten) Rechtsbegehren, es seien die Beschwerdeführerinnen zur Zahlung von USD 6'847'305.29 zuzüglich Zins von 5 % seit 19. Januar 2006 zu verpflichten. Zudem seien die Beilagen C-176 sowie C-177 streng vertraulich zu behandeln.
Die Beschwerdeführerinnen machten widerklageweise Ansprüche aus erfolgten Lieferungen sowie unzutreffenden Preisberechnungen über insgesamt USD 3'830'273.35 zuzüglich Zins geltend.
B.b Mit Schiedsspruch vom 3. April 2009 hiess das ICC Schiedsgericht mit Sitz in Zürich die Schiedsklage teilweise gut und verpflichtete die Beschwerdeführerinnen solidarisch zur Zahlung von Schadenersatz im Betrag vom USD 1'243'824.-- zuzüglich Zins zu 5 % seit dem 19. Januar 2006 (Dispositiv-Ziffer 1). Im Weiteren verpflichtete es die Beschwerdeführerinnen, die Beilagen C-176 und C-177 streng vertraulich zu behandeln (Dispositiv-Ziffer 2) und es wies die Widerklage ab (Dispositiv-Ziffer 3). Im Übrigen entschied es über die Verfahrenskosten (Dispositiv-Ziffern 4 und 5).
Das Schiedsgericht erwog hinsichtlich der von den Beschwerdeführerinnen ausgesprochenen Kündigung, dass die Beschwerdegegnerin zwar die Vereinbarung vom 16. Februar 2001 verletzt habe, indem sie die FCA Preise den Beschwerdeführerinnen nicht offenlegte, dass diese Vertragsverletzung jedoch nicht als "material breach" im Sinne von Ziffer 3(c) der geschlossenen Vereinbarung betrachtet werden könne, weshalb die Kündigung vom 19. Januar 2006 ungerechtfertigt gewesen sei.
Hinsichtlich der Widerklage der Beschwerdeführerinnen gestützt auf angeblich unzutreffende Preisberechnungen bei erfolgten Lieferungen hielt das Schiedsgericht dafür, dass nach Treu und Glauben im Geschäftsverkehr davon auszugehen sei, dass die Beschwerdeführerin 2 den von der Beschwerdegegnerin festgesetzten Preisen vorbehaltlos zugestimmt habe, indem sie diese Preise zur Grundlage ihrer unterzeichneten Rechnungen gemacht und damit auf eine rückwirkende Überprüfung der Preise formgültig verzichtet habe. Eine absichtliche Täuschung nach <ref-law> schloss das Schiedsgericht aus.
C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführerinnen dem Bundesgericht, es seien Dispositiv-Ziffern 1 sowie 3 - 5 des ICC Schiedsspruchs vom 3. April 2009 aufzuheben, "und es sei die Angelegenheit zur Neubeurteilung an das Schiedsgericht zurückzuweisen, wobei dieses anzuweisen sei, im Sinne der Erwägungen des Bundesgerichts die Klage der Beschwerdegegnerin vollumfänglich abzuweisen und die Widerklage der Beschwerdeführerinnen vollumfänglich gutzuheissen". Eventualiter seien die genannten Dispositiv-Ziffern aufzuheben und es sei die Streitsache zur Neubeurteilung an das Schiedsgericht zurückzuweisen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Schiedsgericht hat auf eine Vernehmlassung verzichtet.
D. Mit Verfügung vom 22. Juni 2009 hiess das Bundesgericht das Sicherstellungsbegehren der Beschwerdegegnerin gut. In der Folge überwiesen die Beschwerdeführerinnen den geforderten Betrag von Fr. 35'000.-- als Sicherstellung einer allfälligen Parteientschädigung an die Gerichtskasse.
Mit Verfügung vom 28. Juli 2009 wies das Bundesgericht das Gesuch der Beschwerdeführerinnen um aufschiebende Wirkung ab. Das erneute Gesuch um Erteilung der aufschiebenden Wirkung bzw. das diesbezügliche Wiedererwägungsgesuch wies es mit Verfügung vom 27. Oktober 2009 ebenfalls ab.
Das Gesuch der Beschwerdeführerinnen um Ansetzung einer Frist zur Einreichung einer Replikschrift wurde mit Verfügung vom 21. Oktober 2009 abgewiesen. Am 29. Oktober 2009 reichten die Beschwerdeführerinnen dem Bundesgericht eine Replikschrift ein.

Erwägungen:
1. Die Beschwerde in Zivilsachen ist gegen Entscheide von Schiedsgerichten unter den Voraussetzungen der Art. 190-192 IPRG zulässig (<ref-law>).
1.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Zürich. Die Parteien haben ihren Sitz nicht in der Schweiz. Da sie die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
1.2 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts betrifft, gilt davon allerdings, wie schon im Rahmen der altrechtlichen staatsrechtlichen Beschwerde, eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen kann (<ref-ruling> E. 1b S. 282; <ref-ruling> E. 4 S. 95 f.; Urteile 4A_224/2008 vom 10. Oktober 2008 E. 2.4; 4A_128/2008 vom 19. August 2008 E. 2.3).
Unzulässig ist der von den Beschwerdeführerinnen über die Aufhebung von Dispositiv-Ziffern 1 sowie 3 - 5 hinaus gestellte Antrag, die Angelegenheit sei zur Neubeurteilung an das Schiedsgericht zurückzuweisen und dieses sei anzuweisen, im Sinne der Erwägungen des Bundesgerichts die Klage der Beschwerdegegnerin abzuweisen und die Widerklage der Beschwerdeführerinnen gutzuheissen. Soweit die Beschwerdeführerinnen vom Bundesgericht einen materiellen Entscheid bzw. eine konkrete Anweisung an das Schiedsgericht über die zu treffende Entscheidung begehren, ist auf den Antrag nicht einzutreten.
1.3 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
1.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733; je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
2. Die Beschwerdeführerinnen rügen im Zusammenhang mit der Frage der Rechtmässigkeit ihrer Kündigung einen Verstoss gegen Art. 190 Abs. 2 lit. b bzw. lit. c IPRG.
2.1 Angesichts dessen, dass die Parteien ausdrücklich vereinbart hätten, dass Schweizer Recht zur Anwendung gelange, und zwar so, wie wenn inländische Parteien ("domestic parties") betroffen wären, habe das Schiedsgericht zu Recht festgestellt, dass die Parteien die Anwendbarkeit des Wiener Kaufrechts (Übereinkommen der Vereinten Nationen über Verträge über den internationalen Warenkauf vom 11. April 1980 [WKR; SR 0.221.211.1]) rechtsgültig ausgeschlossen hätten. Dennoch habe das Schiedsgericht die Frage, ob die Vertragsverletzung der Beschwerdegegnerin als wesentliche Vertragsverletzung ("material breach") zu qualifizieren sei, nach Art. 25 WKR entschieden. Indem das Schiedsgericht die eindeutige Rechtswahl der Parteien missachtet habe, habe es seine Kompetenz mit Blick auf seine Zuständigkeit gemäss <ref-law> überschritten. Im Weiteren habe es damit eine Frage entschieden, die ihm seitens der Parteien nicht unterbreitet worden sei, weshalb eine Verletzung von <ref-law> vorliege.
2.2 Die Rüge ist unbegründet. Abgesehen davon, dass ohnehin zweifelhaft ist, ob die von den Beschwerdeführerinnen erhobene Rüge als solche mangelnder Zuständigkeit im Sinne von <ref-law> behandelt werden könnte, da sie eher das Gebiet der Rechtsanwendung betrifft, bezüglich derer lediglich die Rüge gemäss <ref-law> zulässig ist (vgl. Urteil 4P.146/2004 vom 28. September 2004 E. 5.2.2; Pierre A. Karrer, in: Basler Kommentar, 2. Aufl. 2007, N. 312 zu <ref-law>; Anton Heini, in: Zürcher Kommentar, 2. Aufl. 2004, N. 13 zu Art. 187; Berger/Kellerhals, Internationale und interne Schiedsgerichtsbarkeit in der Schweiz, 2006, Rz. 1556; a.M. Berti/Schnyder, in: Basler Kommentar, 2. Aufl. 2007, N. 39 zu <ref-law>), erweist sich bereits die der Rüge zugrunde liegende Behauptung als unzutreffend, das Schiedsgericht habe in Abweichung des gewählten schweizerischen Rechts ausländisches Recht angewendet.
Das Schiedsgericht hat nicht verkannt, dass die Parteien schweizerisches Recht auf ihr Vertragsverhältnis angewendet wissen wollten und dabei die Anwendbarkeit des Wiener Kaufrechts ausschlossen. Es hatte zur Beurteilung der Rechtmässigkeit der von den Beschwerdeführerinnen ausgesprochenen Kündigung Ziffer 3(c) der Vereinbarung vom 16. Februar 2001 auszulegen, die eine Kündigungsmöglichkeit im Fall einer wesentlichen Vertragsverletzung ("material breach") vorsieht.
Nach schweizerischem Recht ist bei der Auslegung einer Vereinbarung zunächst auf den übereinstimmenden wirklichen Parteiwillen abzustellen; bei dessen Fehlen ist die Vertragsklausel in Anwendung des Vertrauensprinzips danach auszulegen, wie sie nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen nach Treu und Glauben verstanden werden durfte und musste (<ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 2.3.2 S. 274 f.; <ref-ruling> E. 3.2 S. 424, 686 E. 4.3.1 S. 689; je mit Hinweisen). Das Schiedsgericht hat ausgehend von der Erwägung, dass der von den Parteien verwendete Begriff des "material breach" im traditionellen schweizerischen Vertragsrecht nicht verwendet werde, dafür gehalten, dass für dessen Auslegung die Umschreibung der wesentlichen Vertragsverletzung ("fundamental breach") nach Art. 25 WKR beigezogen werden könne, obwohl das Wiener Kaufrecht grundsätzlich nicht auf die Vereinbarung anwendbar sei und hat gleichzeitig auf Art. 7.3.1 der Unidroit Principles of International Commercial Contracts verwiesen. Es hat damit beurteilt, wie die Parteien als im internationalen Handelsverkehr tätige Unternehmen den von ihnen verwendeten Begriff verstanden bzw. verstehen durften. Das Schiedsgericht hat damit eine Vertragsauslegung nach Schweizer Recht vorgenommen und nicht entgegen der Rechtswahl der Parteien ausländisches Recht angewendet.
Der Vorwurf, das Schiedsgericht habe die eindeutige Rechtswahl der Parteien missachtet und damit seine Zuständigkeit gemäss <ref-law> überschritten bzw. unter Verletzung von <ref-law> eine Frage entschieden, die ihm nicht unterbreitet worden sei, ist damit unbegründet.
Ins Leere stösst aus diesen Gründen auch die Rüge der Verletzung des Ordre public (<ref-law>), soweit die Beschwerdeführerinnen diese mit der angeblichen Missachtung der Rechtswahlklausel begründen.
3. Die Beschwerdeführerinnen rügen hinsichtlich der Beurteilung ihrer Kündigung sodann eine Verletzung des rechtlichen Gehörs (<ref-law>).
3.1 Sie tragen hierzu vor, sie hätten nicht damit rechnen müssen, dass das Schiedsgericht den Begriff "material breach" in Übereinstimmung mit dem Wiener Kaufrecht auslegen würde, da dieses nicht dem inländischen schweizerischen Recht zuzuordnen sei. Sie hätten daher zur Anwendbarkeit von Art. 25 WKR sowie insbesondere zu den nach dieser Bestimmung relevanten Fragen der subjektiven und objektiven Vorhersehbarkeit der sich aus der Vertragsverletzung ergebenden Nachteile nicht Stellung genommen. Dass die Beschwerdeführerinnen nicht mit einer Auslegung nach dem Wiener Kaufrecht gerechnet hätten und auch nicht damit hätten rechnen müssen, ergebe sich zudem daraus, dass das Schiedsgericht in seiner Verfügung Nr. 19 vom 29. Oktober 2008 diese Frage nicht thematisiert und die Parteien nicht aufgefordert habe, dazu zu plädieren. Parteivorbringen zu Art. 25 WKR, insbesondere hinsichtlich der Vorhersehbarkeit, hätten nach Ansicht der Beschwerdeführerinnen neue tatsächliche Behauptungen erforderlich gemacht, was das Schiedsgericht anlässlich der Verhandlung vom 27. Oktober 2008 wie auch in Ziffer 1.2 Abs. 2 der Verfügung vom 29. Oktober 2008 explizit ausgeschlossen habe. Angesichts dieser Erklärungen und Anordnungen hätten die Beschwerdeführerinnen darauf vertrauen dürfen, diesbezüglich nicht weiter plädieren zu müssen. Das Vorgehen des Schiedsgerichts habe dazu geführt, dass sie sich bezüglich der erwähnten Fragen nicht hätten äussern und in das Verfahren einbringen können.
3.2 Nach bundesgerichtlicher Rechtsprechung besteht kein verfassungsrechtlicher Anspruch der Parteien, zur rechtlichen Würdigung der durch sie in den Prozess eingeführten Tatsachen noch besonders angehört zu werden. Ebenso wenig folgt aus dem Gehörsanspruch, dass die Parteien vorgängig auf den für den Entscheid wesentlichen Sachverhalt hinzuweisen wären. Eine Ausnahme besteht namentlich dann, wenn ein Gericht seinen Entscheid mit einem Rechtsgrund zu begründen beabsichtigt, auf den sich die beteiligten Parteien nicht berufen haben und mit dessen Erheblichkeit sie vernünftigerweise nicht rechnen mussten (<ref-ruling> E. 5 S. 39; <ref-ruling> E. 2c/aa S. 22; <ref-ruling> E. 3c S. 52). Bei der Frage, ob die Rechtsanwendung des Schiedsgerichts als überraschend im Sinne der bundesgerichtlichen Rechtsprechung zu qualifizieren ist, handelt es sich um eine Ermessensfrage, bei deren Beurteilung sich das Bundesgericht auf dem Gebiet der internationalen Schiedsgerichtsbarkeit Zurückhaltung auferlegt. Damit soll den Besonderheiten des Verfahrens - namentlich dem übereinstimmenden Willen der Parteien, ihren Streit nicht vor staatlichen Gerichten auszutragen sowie der Tatsache, dass die Schiedsrichter unterschiedlichen Rechtstraditionen entstammen können - Rechnung getragen sowie verhindert werden, dass das Argument der überraschenden Rechtsanwendung dazu missbraucht wird, eine materielle Überprüfung des Schiedsurteils durch das Bundesgericht zu erwirken (<ref-ruling> E. 5 S. 39 f.; 4A_42/2007 vom 13. Juli 2007 E. 7.1; 4P.260/2000 vom 2. März 2001 E. 6b).
3.3 Das Schiedsgericht hat die in der Vereinbarung vom 16. Februar 2001 enthaltene Vertragsklausel, welche die Voraussetzungen einer ausserordentlichen Kündigung umschreibt, ausgelegt und dafür gehalten, dass mangels einer wesentlichen Vertragsverletzung ("material breach") seitens der Beschwerdegegnerin die ausserordentliche Kündigung nicht gerechtfertigt gewesen sei. Die Frage, ob das Verhalten der Beschwerdegegnerin als "material breach" im Sinne der vereinbarten Klausel zu werten sei und die Vereinbarung vom 16. Februar 2001 von den Beschwerdeführerinnen vorzeitig beendigt werden durfte, war eines der Hauptargumente der Beschwerdeführerinnen gegen die Schadenersatzklage der Beschwerdegegnerin und damit eines der zentralen Themen im Rahmen des Schiedsverfahrens. Sie mussten somit davon ausgehen, dass das Schiedsgericht die vertraglichen Voraussetzungen für eine ausserordentliche Kündigung nach Ziffer 3(c) der Vereinbarung vom 16. Februar 2001 prüfen und dazu den Begriff des "material breach" auslegen würde. Sie hatten daher Anlass, sich zu dieser Frage zu äussern. Nachdem die im internationalen Handel tätigen Parteien den erwähnten Begriff nicht vertraglich umschrieben hatten und dieser im schweizerischen Vertragsrecht nicht gebräuchlich ist, war es naheliegend, für die Auslegung des Begriffs "material breach" das Verständnis im internationalen Handelsverkehr zu berücksichtigen und Art. 25 WKR sowie Art. 7.3.1 der Unidroit Principles of International Commercial Contracts beizuziehen.
Die Auslegung und Anwendung von Ziffer 3(c) der Vereinbarung vom 16. Februar 2001 kam somit nicht überraschend und der Vorwurf der Gehörsverletzung ist unbegründet. Davon, dass die Beschwerdeführerinnen durch die Anordnungen des Schiedsgerichts geradezu davon abgehalten worden wären, zu den erwähnten Punkten Stellung zu nehmen, kann zudem keine Rede sein, zumal die Vorinstanz die Parteien mit besagter Verfügung vom 29. Oktober 2008 im Gegenteil aufgefordert hatte, sich auch in rechtlicher Hinsicht nochmals umfassend zur Streitsache zu äussern.
4. Die Beschwerdeführerinnen rügen im Zusammenhang mit ihrer Kündigung im Weiteren eine Verletzung des Ordre public (<ref-law>).
4.1 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). Gegen den Ordre public verstösst die materielle Beurteilung eines streitigen Anspruchs nur, wenn sie fundamentale Rechtsgrundsätze verkennt und daher mit der wesentlichen, weitgehend anerkannten Wertordnung schlechthin unvereinbar ist, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte. Zu diesen Prinzipien gehören die Vertragstreue (pacta sunt servanda), das Rechtsmissbrauchsverbot, der Grundsatz von Treu und Glauben, das Verbot der entschädigungslosen Enteignung, das Diskriminierungsverbot und der Schutz von Handlungsunfähigen. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 2.2 S. 392 ff.; <ref-ruling> E. 6b S. 198; <ref-ruling> E. 6a S. 166 f.).
4.2 Die Beschwerdeführerinnen berufen sich zu Unrecht auf eine Verletzung des Grundsatzes, dass Dauerschuldverhältnisse aus wichtigen Gründen vorzeitig beendigt werden dürfen (vgl. Urteil 4P.172/1999 vom 17. Februar 2000 E. 5d). Sie räumen selbst ein, dass ihnen das Schiedsgericht nicht grundsätzlich das Recht abgesprochen hat, die Vereinbarung mit der Beschwerdegegnerin ausserordentlich zu kündigen. Vielmehr ist es von der Zulässigkeit einer vorzeitigen Beendigung des Vertragsverhältnisses ausgegangen, hat jedoch dafür gehalten, dass deren Voraussetzungen mangels einer wesentlichen Vertragsverletzung ("material breach") nicht erfüllt seien.
Die Beschwerdeführerinnen verkennen mit ihren weiteren Vorbringen zur vertraglichen Preisoffenlegungspflicht, dass es dem Bundesgericht nicht zusteht, das Auslegungsergebnis, zu dem das Schiedsgericht gelangt ist, auf seine Recht- oder Verfassungsmässigkeit (Willkürverbot) zu überprüfen. Sie kritisieren in appellatorischer Weise die Erwägung der Vorinstanz, wonach die Beschwerdegegnerin trotz unterbliebener Offenlegung der FCA Kaufpreise keine wesentliche Vertragspflicht verletzt habe und die von den Beschwerdeführerinnen ausgesprochene Kündigung daher ungerechtfertigt sei. Abgesehen davon machen sie nunmehr vor Bundesgericht eine unzumutbare Einschränkung ihrer Persönlichkeitsrechte geltend, ohne aufzuzeigen, inwiefern sie sich neben dem Kündigungsgrund des "material breach" bereits im Schiedsverfahren auf entsprechende Behauptungen berufen hätten. Entgegen der in der Beschwerde geäusserten Ansicht hat das Schiedsgericht den Ordre public nicht verletzt, wenn es die Verletzung der Preisoffenlegungspflicht der Beschwerdegegnerin nicht als "material breach" qualifizierte und den Beschwerdeführerinnen gestützt darauf die Berechtigung zur fristlosen Kündigung absprach.
4.3 Auch mit dem Einwand, das Schiedsgericht habe gegen den Ordre public verstossen, weil im Zeitpunkt der Kündigung mangels Bestimmbarkeit des Kaufpreises keine vertragliche Lieferverpflichtung der Beschwerdeführerinnen mehr bestanden habe, üben sie lediglich appellatorische Kritik am angefochtenen Entscheid. Sie stellen damit in unzulässiger Weise die Erwägung des Schiedsgerichts in Frage, wonach der Preis aufgrund der vertraglichen Vorgaben auch im Fall der Überschreitung des Höchstpreises von USD 116.-- genügend bestimmbar gewesen sei. Wenn die Vorinstanz den Schadenersatz infolge ungerechtfertigter Kündigung entsprechend in Anwendung von <ref-law> festsetzte, missachtete sie entgegen der Ansicht der Beschwerdeführerinnen den Grundsatz der Privatautonomie nicht. Ein Verstoss gegen den Ordre public (<ref-law>) ist nicht dargetan.
5. Die Beschwerdeführerinnen machen schliesslich im Zusammenhang mit dem vom Schiedsgericht verworfenen Force Majeure-Einwand, dem Schadenersatzanspruch der Beschwerdegegnerin sowie der von ihnen erhobenen Widerklage eine Verletzung ihres Gehörsanspruchs (<ref-law>) bzw. des Ordre public (<ref-law>) geltend.
5.1 Nach der Rechtsprechung des Bundesgerichts reicht eine offensichtlich falsche oder aktenwidrige Feststellung für sich allein nicht aus, um einen internationalen Schiedsentscheid aufzuheben. Der Anspruch auf rechtliches Gehör enthält keinen Anspruch auf einen materiell richtigen Entscheid. Daher ist es nicht Sache des Bundesgerichts zu überprüfen, ob das Schiedsgericht sämtliche Aktenstellen berücksichtigt und richtig verstanden hat. Erforderlich ist eine formelle Rechtsverweigerung in dem Sinne, dass das rechtliche Gehör der Partei durch das offensichtliche Versehen faktisch ausgehöhlt wurde und die Partei im Ergebnis nicht besser dasteht, als wenn ihr das rechtliche Gehör zu einer entscheidwesentlichen Frage überhaupt nicht gewährt worden wäre. Wer aus einem offensichtlichen Versehen eine Verletzung des rechtlichen Gehörs ableiten will, hat demnach aufzuzeigen, dass ihm das richterliche Versehen verunmöglichte, seinen Standpunkt in Bezug auf ein prozessrelevantes Thema in den Prozess einzubringen und zu beweisen (<ref-ruling> E. 5.2 S. 248 f.; <ref-ruling> E. 2b-f).
5.1 Nach der Rechtsprechung des Bundesgerichts reicht eine offensichtlich falsche oder aktenwidrige Feststellung für sich allein nicht aus, um einen internationalen Schiedsentscheid aufzuheben. Der Anspruch auf rechtliches Gehör enthält keinen Anspruch auf einen materiell richtigen Entscheid. Daher ist es nicht Sache des Bundesgerichts zu überprüfen, ob das Schiedsgericht sämtliche Aktenstellen berücksichtigt und richtig verstanden hat. Erforderlich ist eine formelle Rechtsverweigerung in dem Sinne, dass das rechtliche Gehör der Partei durch das offensichtliche Versehen faktisch ausgehöhlt wurde und die Partei im Ergebnis nicht besser dasteht, als wenn ihr das rechtliche Gehör zu einer entscheidwesentlichen Frage überhaupt nicht gewährt worden wäre. Wer aus einem offensichtlichen Versehen eine Verletzung des rechtlichen Gehörs ableiten will, hat demnach aufzuzeigen, dass ihm das richterliche Versehen verunmöglichte, seinen Standpunkt in Bezug auf ein prozessrelevantes Thema in den Prozess einzubringen und zu beweisen (<ref-ruling> E. 5.2 S. 248 f.; <ref-ruling> E. 2b-f).
5.2 5.2.1 Das Schiedsgericht hielt im Zusammenhang mit dem Force Majeure-Einwand der Beschwerdeführerinnen hinsichtlich ihrer Lieferverpflichtung vom Oktober 2005 fest, diese hätten nicht hinreichend substantiiert, dass die von ihnen behauptete Trockenheit eine Force Majeure-Situation darstellen würde; so hätten sie es etwa unterlassen, statistische Informationen einzureichen, die zeigten, dass die meteorologische Situation in der Region Zeerust im relevanten Zeitraum erheblich und unvorhersehbar von den normalen Fluktuationen abwich.
Was die Beschwerdeführerinnen hiergegen vorbringen, ist nicht geeignet, eine Gehörsverletzung darzutun. Auch die von ihnen in der Beschwerdeschrift aufgelisteten Vorbringen im Rahmen des Schiedsverfahrens zeigen nicht konkret auf, inwieweit die Niederschlagsmenge im massgebenden Zeitraum von den meteorologischen Werten abwich, sondern beschreiben lediglich in allgemeiner Weise die angeblichen Produktionsprobleme infolge Trockenheit. Einen Bezug zu üblichen saisonalen Fluktuationen stellen ihre Behauptungen nicht her. Inwiefern das Schiedsgericht die Vorbringen der Beschwerdeführerinnen in einer Weise übersehen haben soll, die es ihnen verunmöglichte, ihren Standpunkt hinsichtlich der Frage der Force Majeure-Situation in das Verfahren einzubringen, ist nicht dargetan. In Tat und Wahrheit zielen die Ausführungen der Beschwerdeführerinnen nicht auf die tatsächlichen Feststellungen des Schiedsgerichts ab, sondern stellen dessen rechtliche Würdigung hinsichtlich der Substantiierung des behaupteten Rechtshinderungsgrunds in Frage. Die Rüge geht fehl.
5.2.2 Die Beschwerdeführerinnen zeigen zudem keine Gehörsverletzung auf, wenn sie vorbringen, die Beschwerdegegnerin habe, soweit ersichtlich, nie bestritten, dass die Mine der Beschwerdeführerin 2 im Winter 2005 und namentlich im Oktober/November 2005 unter einer derart ausgeprägten Trockenheit zu leiden gehabt habe, dass ihre Produktion erheblich eingeschränkt worden sei. Sie legen nicht dar, welches ihrer eigenen Vorbringen damit im schiedsgerichtlichen Verfahren übergangen worden wäre und inwiefern sie selbst ihren Standpunkt nicht hätten in das Verfahren einbringen können.
5.2.3 Wenn die Beschwerdeführerinnen im Weiteren vorbringen, das Schiedsgericht habe eine Force Majeure-Situation zufolge ihrer Lieferungen an andere Abnehmer zu Unrecht verneint und es habe unzutreffend festgestellt, das Exportvolumen der Beschwerdeführerinnen sei erst im November/Dezember 2005 gesunken, zeigen sie ebenfalls keine Gehörsverletzung auf. Sie kritisieren vielmehr unter Berufung auf verschiedene angeblich "offensichtliche Versehen" und "offensichtlich falsche und aktenwidrige Feststellungen" die Schlüsse der Vorinstanz, begründen jedoch nicht, inwiefern ihnen verunmöglicht worden sein soll, ihren Standpunkt hinsichtlich der Frage der Force Majeure-Situation in das Verfahren einzubringen.
5.3 Das Schiedsgericht hat erwogen, dass für Flussspat angesichts der in der Zeitschrift "Industrial Minerals" publizierten Preise ein Verkäuflichkeitspreis im Sinn von <ref-law> bestehe. Entsprechend hat es der Beschwerdegegnerin zugestanden, ihren Schadenersatzanspruch ohne den Nachweis konkreter Deckungskäufe nach der Differenz zwischen dem vertraglich geschuldeten Preis und dem Verkäuflichkeitspreis zu berechnen.
Die Beschwerdeführerinnen verkennen die Begründungsanforderungen an eine Gehörsrüge (Art. 77 Abs. 3 i.V.m. <ref-law>) sowie den Umfang der bundesgerichtlichen Überprüfungsbefugnis, wenn sie eine Behauptung der Beschwerdegegnerin sowie eigene ausführliche Vorbringen zur Frage des Marktpreises im Rahmen des Schiedsverfahrens vor Bundesgericht wörtlich wiederholen, gestützt darauf geltend machen, das Schiedsgericht habe sich mit diesen Darlegungen nicht bzw. nur unzureichend auseinandergesetzt und anschliessend hinsichtlich des Beweisergebnisses sowie der Anwendung von <ref-law> vom angefochtenen Entscheid abweichende Schlüsse ziehen. Damit kritisieren sie - wiederum unter Berufung auf verschiedene angeblich "offensichtliche Versehen" und "offensichtlich falsche und aktenwidrige Feststellungen" - lediglich in appellatorischer Weise das Beweisergebnis sowie die rechtliche Beurteilung des Schiedsgerichts. Auch mit ihrer Behauptung, die Darlegungen der Beschwerdegegnerin zur Frage des Marktpreises seien nicht gehörig substantiiert gewesen, machen sie keine Gehörsverletzung geltend. Die Beschwerdeführerinnen legen einfach ihren eigenen Standpunkt nochmals dar und behaupten, dieser sei durch die Akten erstellt. Dies ist im Rahmen der Schiedsbeschwerde nicht zulässig.
Die Beschwerdeführerinnen verkennen mit ihren Vorbringen zudem, dass es nicht Sache des Bundesgerichts ist zu überprüfen, ob das Schiedsgericht sämtliche Aktenstellen berücksichtigt und richtig verstanden hat (<ref-ruling> E. 5.2 S. 249; <ref-ruling> E. 2 S. 578). Dass das Schiedsgericht zu den verschiedenen Argumenten der Beschwerdeführerinnen, weshalb nach ihrer Ansicht kein Verkäuflichkeitspreis im Sinne von <ref-law> bestehe, nicht ausdrücklich Stellung genommen hat, verletzt den Gehörsanspruch nicht. Das Schiedsgericht hat die Hauptargumente der Beschwerdeführerinnen im angefochtenen Entscheid unter Verweis auf ihren 1. Post-Hearing Brief zusammengefasst und eingehend begründet, weshalb ein Verkäuflichkeitspreis nach <ref-law> vorliege. Einer ausdrücklichen Widerlegung sämtlicher Argumente der Beschwerdeführerinnen bedurfte es nicht (vgl. <ref-ruling> E. 6.2 S. 188). Ebenso wenig hätte das Schiedsgericht die Parteien in seiner Verfügung vom 29. Oktober 2008 nochmal eigens auffordern müssen, weitere Darlegungen zum Vorliegen eines Marktpreises bzw. zur Frage zu machen, ob aus der Zeitschrift "Industrial Minerals" auf einen solchen geschlossen werden könne. Die Gehörsrüge im Zusammenhang mit dem Schadenersatzanspruch der Beschwerdegegnerin stösst ins Leere.
5.4 Die Beschwerdeführerinnen rügen hinsichtlich ihrer Widerklage sowohl eine Verletzung ihres Gehörsanspruchs als auch des Ordre public.
5.4.1 Das Schiedsgericht hat erwogen, dass die Beschwerdegegnerin die von ihr berechneten Preise der Beschwerdeführerin 2 zwar ohne Berechnungsgrundlagen übermittelte, dass Letztere jedoch bis Oktober 2005 ihre Rechnungen jeweils gestützt darauf ohne jegliche Vorbehalte hinsichtlich einer Nachberechnung des Preises ausstellte. Dieses Verhalten sei nach Treu und Glauben als unbedingte Zustimmung der Beschwerdeführerin 2 zu den von der Beschwerdegegnerin festgesetzten Preisen zu werten. Mit jeder vorbehaltlosen Rechnungsstellung habe die Beschwerdeführerin 2 auf eine nachträgliche Überprüfung der gestellten Preise anhand der vereinbarten Preisberechnungsformel verzichtet.
Ein offensichtliches Versehen bzw. eine aktenwidrige Feststellung, die zu einem anderen Ergebnis führen würde, ergibt sich aus den Vorbringen der Beschwerdeführerinnen nicht. Sie wehren sich gegen die vorinstanzliche Feststellung in anderem Zusammenhang, wonach unbestritten sei, dass die Beschwerdeführerin 2 ihr erstes formelles Begehren um Offenlegung der FCA Preise für die Jahre 2002 - 2004 am 12. Oktober 2005 gestellt habe, und bringen hiergegen mit Verweis auf ihre Eingaben sowie verschiedene Aktenstücke vor, sie hätten im schiedsgerichtlichen Verfahren geltend gemacht, die Beschwerdegegnerin schon vor Beginn des Vertragsjahres 2002 aufgefordert zu haben, die FCA Preise bekannt zu geben, damit der Preis für das Vertragsjahr 2002 errechnet werden könne bzw. sie hätten am 19. Juni 2003 erneut die Bekanntgabe der FCA Preise verlangt, um den Preis für das Vertragsjahr 2003 zu berechnen. Weder diese Behauptungen noch die in der 1. Rechtsschrift sowie dem 1. Post-Hearing Brief erwähnten weiteren Versuche, die Beschwerdegegnerin zur Bekanntgabe der FCA Preise anzuhalten, waren jedoch entscheidend für die Erwägung des Schiedsgerichts, es sei von einem Verzicht der Beschwerdeführerinnen auf Nachprüfung auszugehen. Wie die Beschwerdegegnerin zu Recht einwendet, beziehen sich die erwähnten Aufforderungen lediglich auf die Bekanntgabe der Preise für das laufende oder kommende Vertragsjahr, jedoch nicht auf die rückwirkende Offenlegung der zugrunde liegenden FCA Preise für die Nachberechnung anhand der Preisberechnungsformel. Es ist daher kein offensichtlicher Widerspruch zur Feststellung des Schiedsgerichts erkennbar, die Beschwerdeführerin 2 habe bis Oktober 2005 jeweils anhand der von der Beschwerdegegnerin berechneten Preise und ohne Vorbehalt hinsichtlich einer Nachberechnung gemäss der vertraglichen Preisberechnungsformel Rechnungen ausgestellt.
Mangels aktenwidriger bzw. offensichtlich unrichtiger Sachverhaltsfeststellung im Zusammenhang mit der von der Vorinstanz angenommenen vorbehaltlosen Zustimmung der Beschwerdeführerin 2 zur Preisfestsetzung der Beschwerdegegnerin erweist sich auch die darauf gestützte Gehörsrüge als unbegründet.
5.4.2 Die Beschwerdeführerinnen begründen ihre Gehörsrüge sodann damit, das Schiedsgericht habe zu Unrecht gefolgert, sie hätten aufgrund des öffentlich zur Verfügung stehenden Zahlenmaterials die Preise abschätzen können, welche die Beschwerdegegnerin anderen Lieferanten bezahlt habe. Sie zeigen jedoch nicht auf, inwiefern ihnen das behauptete offensichtliche Versehen verunmöglichte, ihren Standpunkt in Bezug auf ein prozessrelevantes Thema in den Prozess einzubringen und zu beweisen (<ref-ruling> E. 5.2 S. 248 f.; <ref-ruling> E. 2b-f).
5.4.3 Die Beschwerdeführerinnen werfen der Vorinstanz schliesslich auch in diesem Zusammenhang zu Unrecht unter Berufung auf den Grundsatz von Treu und Glauben eine Verletzung des Ordre public (<ref-law>) vor.
Sie kritisieren unter Hinweis auf verschiedene andere Erwägungen des angefochtenen Entscheids sowie eigene Vorbringen im Rahmen des Schiedsverfahrens die vorinstanzlichen Schlussfolgerungen, das Verhalten der Beschwerdeführerin 2 sei als Verzicht auf eine Nachkalkulation zu werten bzw. die Beschwerdegegnerin habe die Beschwerdeführerinnen nicht nach <ref-law> getäuscht und unterbreiten dem Bundesgericht ihre eigene Sicht der Dinge.
Das Schiedsgericht hat das Verhalten der Beschwerdeführerin 2 unter Berücksichtigung des Umstands, dass die Beschwerdegegnerin die FCA Preise entgegen der Vereinbarung vom 16. Februar 2001 nicht offenlegte und die von ihr bezahlten Preise der Beschwerdeführerin 2 ohne Berechnungsgrundlagen übermittelte, nach dem Vertrauensprinzip gewürdigt und einen Verzicht auf Nachkalkulation angenommen. Es hat dabei den Grundsatz von Treu und Glauben berücksichtigt, jedoch andere Schlüsse gezogen als die Beschwerdeführerinnen. Ihre Vorbringen zielen darauf ab, die wesentlichen Sachverhaltsfeststellungen sowie die rechtliche Beurteilung des Verhaltens der Beschwerdeführerin 2 bei der Rechnungsstellung im angefochtenen Entscheid zu kritisieren, was im Beschwerdeverfahren nicht zulässig ist, da das Bundesgericht auch im Rahmen der Rüge der Ordre public-Widrigkeit (<ref-law>) Tat- und Rechtsfragen nicht wie eine Berufungsinstanz überprüfen kann (vgl. dazu E. 4.1).
6. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang werden die Beschwerdeführerinnen unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).
Die Parteientschädigung ist auf Fr. 35'000.-- festzusetzen und aus der an die Gerichtskasse bezahlten Sicherheitsleistung auszurichten. Diese Entschädigung erscheint entgegen der Ansicht der Beschwerdegegnerin auch unter Berücksichtigung der verschiedenen Eingaben der Beschwerdeführerinnen zur Frage der aufschiebenden Wirkung sowie des Umfangs der Beschwerde als angemessen (vgl. Art. 3 Abs. 1 des Reglements über die Parteientschädigung und die Entschädigung für die amtliche Vertretung im Verfahren vor dem Bundesgericht [SR 173.110.210.3]).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 30'000.-- werden den Beschwerdeführerinnen auferlegt (unter solidarischer Haftbarkeit und intern je zur Hälfte).
3. Die Beschwerdeführerinnen haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren (unter solidarischer Haftbarkeit und intern je zur Hälfte) mit Fr. 35'000.-- zu entschädigen. Diese Entschädigung wird aus der an die Gerichtskasse bezahlten Sicherheitsleistung ausgerichtet.
4. Dieses Urteil wird den Parteien und dem ICC Schiedsgericht mit Sitz in Zürich schriftlich mitgeteilt.
Lausanne, 16. Dezember 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann