Sachverhalt:
A. Die X._ AG (Beschwerdeführerin; Verkäuferin) mit Sitz in Basel und die Y._ SA (Beschwerdegegnerin; Käuferin) mit Sitz in Spanien schlossen am 12. Dezember 2000 einen Vertrag über die Lieferung einer Abfüll- und Verpackungsanlage. Der Kaufpreis der gesamten Anlage betrug Pts 247'278'337.-- (entsprechend EUR 1'486'172.74). Die Anlage umfasste zehn Maschinen sowie die Transport- und Verbindungssysteme zwischen diesen. Die Beschwerdeführerin hatte die Verpackungslinie zu installieren und in Betrieb zu setzen.
Nach der Installation der Anlage wollte die Beschwerdeführerin einen Abnahmelauf durchführen, wobei sich die Parteien über die zu erreichende Produktionsleistung uneinig waren. Die Beschwerdegegnerin bestand im Wesentlichen auf einer Leistungsfähigkeit der gesamten Anlage von 180 Flacons pro Minute. Die Beschwerdeführerin erklärte, dass eine solche Gesamtleistung weder möglich noch vereinbart sei. Sie unternahm diverse Versuche, die deutlich unter dem Wert von 180 Flacons pro Minute liegende Leistung zu erhöhen. Am 23. März 2003 erklärte die Beschwerdegegnerin die Auflösung des Vertrags und forderte die Rückzahlung des bereits bezahlten Kaufpreises nebst Schadenersatz. Am 9. Februar 2004 leitete die Beschwerdegegnerin die Betreibung ein.
B. Mit Eingabe vom 5. August 2004 erhob die Beschwerdegegnerin Klage beim Zivilgericht Basel-Stadt. Sie beantragte, die Beschwerdeführerin zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 22. Januar 2001 sowie zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 19. November 2001, Zug um Zug gegen Rückgabe der von der Beschwerdeführerin gelieferten Maschinenanlage gemäss dem zwischen den Parteien geschlossenen Kaufvertrag vom 12. Dezember 2000, zu verurteilen. Zudem sei die Beschwerdeführerin zur Zahlung von EUR 110'393.48 zuzüglich 5 % Zins seit dem 25. März 2003, zur Zahlung von EUR 13'007.20 zuzüglich 5 % Zins seit dem 10. Februar 2004 sowie zur Zahlung von EUR 177'632.37 zuzüglich 5 % Zins seit dem 22. Juni 2004, Mehrforderung vorbehalten, zu verpflichten (Wandelung). Eventuell sei die Beschwerdeführerin zur Zahlung von EUR 1'301'450.77 zuzüglich 5 % Zins seit dem 1. Oktober 2001, zur Zahlung von EUR 13'007.20 zuzüglich 5 % Zins seit dem 10. Februar 2004 und zur Zahlung von EUR 177'632.37 zuzüglich 5 % Zins seit dem 22. Juni 2004, Mehrforderung vorbehalten, abzüglich der letzten Kaufpreisrate von EUR 495'390.91, zu verurteilen (Minderung). Die Beschwerdeführerin forderte ihrerseits widerklageweise den Restpreis sowie Entschädigungen. Sie beantragte, die Beschwerdegegnerin auf Bezahlung von EUR 731'675.19 nebst gestaffeltem Zins zu verurteilen, vorbehältlich einer Mehrforderung. Mit Urteil vom 8. November 2006 erkannte das Zivilgericht Folgendes:
1. In Gutheissung der Klage wird die Beschwerdeführerin zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 22. Januar 2001, sowie zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 19. September 2001, Zug um Zug gegen Rückgabe der von der Beschwerdeführerin gelieferten Maschinenanlage gemäss dem zwischen den Parteien geschlossenen Kaufvertrag vom 12. Dezember 2000; zur Zahlung von EUR 110'393.48 zuzüglich 5 % Zins seit dem 25. März 2003; zur Zahlung von EUR 13'007.20 zuzüglich 5 % Zins seit dem 10. Februar 2004; zur Zahlung von EUR 177'632.37 zuzüglich 5 % Zins seit dem 22. Juni 2004 an die Beschwerdegegnerin verurteilt.
2. Die Widerklage wird abgewiesen.
Gegen dieses Urteil des Zivilgerichts gelangte die Beschwerdeführerin an das Appellationsgericht des Kantons Basel-Stadt. Sie beantragte, das Urteil des Zivilgerichts aufzuheben. Die Klage sei abzuweisen und die Beschwerdegegnerin widerklageweise zu verurteilen, ihr EUR 731'675.19 nebst gestaffeltem Zins zu bezahlen. Das Appellationsgericht bestätigte am 26. September 2008 das erstinstanzliche Urteil.
C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin, das Urteil des Appellationsgerichts vom 26. September 2008 aufzuheben. Die Klage sei abzuweisen und die Widerklage sei zur erneuten Entscheidung an das Appellationsgericht zurückzuweisen. Eventualiter seien die Klage und die Widerklage zur erneuten Entscheidung an das Appellationsgericht zurückzuweisen.
Die Beschwerdegegnerin stellt das Begehren, die Beschwerde abzuweisen und das Urteil des Appellationsgerichts zu bestätigen. Das Appellationsgericht schliesst auf Abweisung der Beschwerde.
D. Der Beschwerde wurde mit Präsidialverfügung vom 9. April 2009 superprovisorisch die aufschiebende Wirkung gewährt.

Erwägungen:
1. Mit dem heutigen Entscheid in der Sache wird das Gesuch, der Beschwerde aufschiebende Wirkung zuzuerkennen, gegenstandslos.
2. 2.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (Art. 42 Abs. 2 BGG). Die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht kann das Bundesgericht nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG; <ref-ruling> E. 2.2; <ref-ruling> E. 3.2).
2.2 Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substantiiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3, 393 E. 7.1 S. 398, 462 E. 2.4).
2.3 Willkür im Sinne von Art. 9 BV liegt nach ständiger Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür nur auf, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Willkür liegt zudem nur vor, wenn nicht bloss die Begründung eines Entscheids, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 5.4 S. 148; <ref-ruling> E. 3.1; <ref-ruling> E. 2.1; je mit Hinweisen).
Zu beachten ist, dass dem Sachgericht im Bereich der Beweiswürdigung ein erheblicher Ermessensspielraum zusteht (<ref-ruling> E. 4b S. 40). Das Bundesgericht greift auf Beschwerde hin nur ein, wenn das Sachgericht sein Ermessen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (vgl. BGE <ref-ruling> E. 2.1; <ref-ruling> E. 2.1; <ref-ruling> E. 4b S. 40).
3. Die Vorinstanz beurteilte den vorliegenden Sachverhalt nach dem Übereinkommen der Vereinten Nationen über Verträge über den internationalen Warenkauf, abgeschlossen in Wien am 11. April 1980 (CISG; SR 0.221.211.1). Die Anwendbarkeit des CISG ist unter den Parteien unbestritten und zu bestätigen (vgl. Art. 1 Abs. 1 lit. a i.V.m. Art. 3 CISG).
4. Vorliegend ist umstritten, ob die Beschwerdegegnerin mit ihrer Erklärung vom 23. März 2003 den Vertrag über die Lieferung einer Abfüll- und Verpackungsanlage vom 12. Dezember 2000 rechtmässig aufgehoben hat. Die Beschwerdeführerin stellt sich auf den Standpunkt, dass die Vorinstanz dies zu Unrecht bejaht habe. Sie rügt eine Verletzung von Art. 8, 25, 49 Abs. 2 lit. b, Art. 82 Abs. 1, Art. 84 Abs. 2 CISG sowie von Art. 210 Abs. 1 OR i.V.m. Art. 116 ff. und 148 IPRG. Zudem erhebt sie mehrere Sachverhaltsrügen.
5. Die Vorinstanz kam bezüglich des Gegenstandes der vereinbarten Leistung der Abfüll- und Verpackungsanlage zum Schluss, dass sich die Parteien übereinstimmend auf eine Produktionslinie mit einem Gesamtausstoss von 180 Einheiten pro Minute geeinigt haben. Unbestrittenermassen habe die Anlage diese vereinbarte Leistung nicht erbracht. Die Vorinstanz schützte die Erwägungen des Zivilgerichts zum Vertragsrücktritt, wonach die Beschwerdegegnerin sowohl gestützt auf Art. 49 Abs. 1 lit. b CISG wegen Nichtlieferung als auch gestützt auf Art. 49 Abs. 1 lit. a CISG wegen wesentlicher Vertragsverletzung zur Aufhebung des Vertrags berechtigt gewesen sei. Die Vorinstanz erwog weiter, eine Verwirkung des Rechts zur Vertragsaufhebung nach Art. 82 CISG liege nicht vor und die Beschwerdeführerin vermöge mit ihrer Verjährungseinrede nicht durchzudringen. Betreffend die Widerklage hielt die Vorinstanz dafür, die Beschwerdeführerin habe die widerklageweise geltend gemachte und eventualiter zur Verrechnung gestellte Gegenforderung weder substantiiert noch unter Beweis gestellt.
6. Die Zulässigkeit der Aufhebung des Vertrags bejahte die Vorinstanz zum einen infolge Nichtlieferung und zum anderen infolge wesentlicher Vertragsverletzung. Das Recht auf Aufhebung des Vertrags gestützt auf Nichtlieferung erachtete sie als gegeben, da die Parteien im Vertrag den Lieferungszeitpunkt abweichend vom CISG als Tag definierten, an dem alle Geräte vollständig bei der Beschwerdegegnerin installiert seien und zur vollen Zufriedenheit arbeiten würden. Folglich sei die Maschinenanlage gar nie geliefert worden. Die Beschwerdegegnerin rügt dazu insbesondere, die Vorinstanz habe die entsprechende Vertragsklausel in Verletzung von Art. 8 Abs. 2 und 3 CISG ausgelegt. Wie es sich damit verhält resp. ob vorliegend die Vertragsaufhebung infolge Nichtlieferung (Art. 49 Abs. 1 lit. b CISG) zulässig wäre, kann offen bleiben. Denn wie sich im Folgenden erweisen wird, war die Beschwerdegegnerin berechtigt, aufgrund wesentlicher Vertragsverletzung (Art. 49 Abs. 1 lit. a CISG) vom Vertrag zurückzutreten.
7. Die Beschwerdeführerin rügt, die Vorinstanz sei zu Unrecht zum Schluss gekommen, dass die Beschwerdegegnerin infolge wesentlicher Vertragsverletzung vom Vertrag habe zurücktreten können. Sie sieht Art. 25 CISG verletzt, da die Vorinstanz die Wesentlichkeit der Vertragsverletzung bejahte.
7.1 Nach Art. 49 Abs. 1 lit. a CISG kann der Käufer die Aufhebung des Vertrags erklären, wenn die Nichterfüllung einer dem Verkäufer nach dem Vertrag oder dem CISG obliegenden Pflicht eine wesentliche Vertragsverletzung darstellt. Wesentlich ist eine Vertragsverletzung nach Art. 25 CISG dann, wenn sie für die andere Partei einen solchen Nachteil zur Folge hat, dass ihr im Wesentlichen entgeht, was sie nach dem Vertrag hätte erwarten dürfen, es sei denn, dass die vertragsbrüchige Partei diese Folge nicht vorausgesehen hat und eine vernünftige Person in gleicher Stellung diese Folge unter den gleichen Umständen auch nicht vorausgesehen hätte.
Der Begriff der wesentlichen Vertragsverletzung nach Art. 25 CISG ist restriktiv auszulegen. Liegen Zweifel vor, ob eine wesentliche Vertragsverletzung gegeben ist, ist davon auszugehen, dass eine solche nicht vorliegt (Urteil 4C.105/2000 vom 15. September 2000 E. 2c/aa). Es ist im Auge zu behalten, dass das UN-Kaufrecht vom Vorrang der Vertragserhaltung ausgeht: Der Vertrag soll im Zweifel auch bei Störungen Bestand haben, die Vertragsaufhebung hingegen die Ausnahme sein. Der Käufer soll in erster Linie die anderen Rechtsbehelfe, namentlich Minderung und Schadenersatz, in Anspruch nehmen, während die Rückabwicklung ihm als letzte Möglichkeit zur Verfügung steht, um auf eine Vertragsverletzung der anderen Partei zu reagieren, die so gewichtig ist, dass sie sein Erfüllungsinteresse im Wesentlichen entfallen lässt. Ob in der gegebenen Situation die Vertragsverletzung nach dem dargelegten Massstab wesentlich und die schärfste Sanktion der Vertragsaufhebung gerechtfertigt ist, hängt dabei entscheidend von den konkreten Umständen des Einzelfalls ab (Urteil 4C.179/1998 vom 28. Oktober 1998 E. 2b mit Hinweisen).
Das zentrale Tatbestandselement von Art. 25 CISG liegt darin, ob der vertragstreuen Partei im Wesentlichen entgeht, was sie nach dem Vertrag hätte erwarten dürfen. Dabei kommt es nicht auf die subjektive Einschätzung an, sondern ist ein objektivierter Massstab anzulegen (Urteil 4C.179/1998 vom 28. Oktober 1998 E. 2a mit Hinweis). Nur Warenmängel von erheblichem Gewicht erfüllen in der Regel die Voraussetzungen von Art. 25 CISG (Brunner, UN-Kaufrecht - CISG, 2004, N. 8 und 16 zu Art. 25 CISG; Staudinger/Magnus, Kommentar zum Bürgerlichen Gesetzbuch, Wiener UN-Kaufrecht, 2005, N. 26 zu Art. 25 CISG). Dazu zählen insbesondere solche Mängel, die mit zumutbarem Aufwand in angemessener Frist nicht behoben werden können, so dass die Ware praktisch unbrauchbar oder unverkäuflich oder ihr Weiterverkauf jedenfalls nicht zumutbar ist (Brunner, a.a.O., N. 16 zu Art. 25 CISG; Staudinger/Magnus, a.a.O., N. 26 zu Art. 25 CISG; vgl. auch Schlechtriem/Schroeter, in: Schlechtriem/Schwenzer, Kommentar zum Einheitlichen UN-Kaufrecht, 5. Aufl. 2008, N. 27 zu Art. 25 CISG). Ist die Ware für die eigene Produktion bzw. die Bedürfnisse des Käufers oder für den Weiterverkauf durch ihn ungeeignet, kann der Käufer den Vertrag aufheben. Bei der Prüfung der Frage, ob für den Käufer die Absetzbarkeit oder Verwendbarkeit der mangelhaften Ware noch zumutbar ist, ist insbesondere darauf abzustellen, ob der Käufer Wiederverkäufer (Händler) oder Produzent bzw. Endabnehmer für die jeweilige Ware ist. Die Verwendbarkeit bzw. Veräusserbarkeit minderwertiger Ware für einen Produzenten oder Endabnehmer, der nicht mit den bezogenen Komponenten oder Materialien handelt, wird in der Regel zu verneinen sein (Brunner, a.a.O., N. 16 zu Art. 25 CISG).
7.2 Die Vorinstanz schützte die Ausführungen des Zivilgerichts zur Annahme einer wesentlichen Vertragsverletzung vollumfänglich. Das Zivilgericht erwog, die tatsächliche Leistung der Anlage sei weit hinter der vertraglich vereinbarten zurückgeblieben. Auch wenn eine Maximalgeschwindigkeit von 115 Flacons pro Minute möglich sei, wie dies der Videofilm nahe lege, sei der von der Beschwerdegegnerin dargelegte Langzeitdurchschnitt von 52 Flacons pro Minute entscheidend. Die Beschwerdegegnerin belege die Produktionsleistungen mit einer ausführlichen Dokumentation. Dieser sei zu entnehmen, dass die durchschnittlichen Produktionsgeschwindigkeiten von Stunde zu Stunde zum Teil stark schwankten, was insbesondere auf die hohe Störanfälligkeit hinweise, was wiederum erkläre, warum mit tiefer Geschwindigkeit gefahren werden musste. Gegenüber der vereinbarten Leistung von 180 Falcons pro Minute bedeute der tatsächlich zu erreichende Durchsatz von 52 Flacons pro Minute eine Produktionseinbusse von 71 %. Selbst wenn bei der Beurteilung der Vertragsmässigkeit der Anlage nicht auf den langjährigen Durchschnitt abgestellt werde, sondern auf eine maximal zu erreichende Geschwindigkeit von 115 Flacons pro Minute, so ergebe sich doch unter Berücksichtigung der verlängerten Stillstandszeiten (bei Chargen von 8 Stunden und um das eineinhalbfache verlängerte Stillstandszeiten) immer noch eine Produktionseinbusse von rund 40 %. Nach der Klageantwort der Beschwerdeführerin soll es sich bei der Anlage um eine automatisierte, kontinuierlich produzierende Hochpräzisionsanlage handeln. Von einer solchen habe die Beschwerdegegnerin erwarten dürfen, dass sie die zugesicherte Leistung auch wirklich erbringe. Dies sei jedoch bei weitem nicht der Fall. Der Beschwerdegegnerin entgehe somit im Wesentlichen, was sie von der Anlage erwarten durfte. Sie hätte den Vertrag nicht geschlossen, wenn sie die tatsächliche Leistungsfähigkeit der Anlage gekannt hätte, denn schon die alte Anlage, die von der Beschwerdegegnerin bisher für die Konfektionierung der drei fraglichen Produkte benutzt worden sei, habe eine ähnliche Leistungsfähigkeit aufgewiesen. Minderung komme schon deshalb nicht in Frage, weil die Produktivitätseinbusse innerhalb der Lebensdauer der Anlage den Kaufpreis bei weitem übersteigen dürfte. Ein Weiterverkauf und eine teilweise Schadloshaltung sei der Beschwerdegegnerin ebenfalls nicht möglich, weshalb eine wesentliche Vertragsverletzung vorliege.
7.3 Unbestritten ist, dass die Beschwerdeführerin den Vertrag vom 12. Dezember 2000 verletzt hat, indem sie eine Maschinenanlage lieferte, die nicht die vertraglich vereinbarte Produktionsleistung erbringt. Die Frage nach der vertraglich vereinbarten Leistung der Abfüll- und Verpackungsanlage war zwischen den Parteien im kantonalen Verfahren ein Hauptstreitpunkt. Nach einer umfassenden Beweiswürdigung kam die Vorinstanz zum Schluss, dass die Parteien eine Produktion von 180 Flacons pro Minute vereinbart haben. Die Beschwerdeführerin verzichtet in ihrer Beschwerdeschrift ausdrücklich auf die Anfechtung dieser vorinstanzlichen Tatsachenfeststellung.
Bestritten ist vorliegend indessen die tatsächliche Leistung der Abfüll- und Verpackungsanlage. Die Vorinstanz ging mit dem Zivilgericht von einem Langzeitdurchschnitt von 52 Flacons pro Minute aus.
7.4 Die Sachverhaltsfeststellung, dass die Maschinenanlage durchschnittlich 52 Flacons pro Minute produziert, rügt die Beschwerdeführerin als willkürlich.
Mit ihren Ausführungen gelingt es der Beschwerdeführerin jedoch nicht, Willkür aufzuzeigen. Es trifft nicht zu, dass die Vorinstanz resp. das Zivilgericht (auf das die Vorinstanz verwies) ohne Beweiswürdigung auf eine durchschnittliche Leistung von 52 Flacons pro Minute geschlossen hat. Vielmehr hat das Zivilgericht namentlich die von der Beschwerdegegnerin ins Recht gelegten Produktions- und Arbeitszeiterfassungsblätter für einen Zeitraum von zweieinhalb Jahren gewürdigt. Ebenso hat sie auch das Video der Beschwerdeführerin in Betracht gezogen. Entgegen der Auffassung der Beschwerdeführerin ist es nicht willkürlich, dass das Zivilgericht daraus nicht folgern konnte, eine Verarbeitungsgeschwindigkeit von 115 Flacons pro Minute sei erstellt. Das Video gab dafür nämlich lediglich Hinweise und legte eine solche Geschwindigkeit jedenfalls nur kurzzeitig nahe. Inwiefern es offensichtlich unhaltbar wäre, auf die Excel-Tabelle und die Zeiterfassungsblätter abzustellen und von einem Referenzzeitraum von mehreren Jahren auszugehen, zeigt die Beschwerdeführerin zudem nicht klar und substantiiert auf. Zu der Excel-Tabelle und den Zeiterfassungsblättern bringt sie lediglich vor, sie habe deren Richtigkeit bestritten. Sie legt aber nicht dar, inwiefern es stossend wäre, darauf abzustellen. Auch mit ihrem Argument, wonach es die Beschwerdegegnerin abgelehnt habe, Testläufe über 150 bzw. 145 Flacons pro Minute mit der Anlage durchzuführen, vermag sie keine Willkür aufzuzeigen. Ihre entsprechenden Rügen beschränken sich auf blosse appellatorische Kritik, womit sie nicht zu hören ist (vgl. Erwägung 2). Weiter bringt die Beschwerdeführerin vor, obwohl sie das Einholen einer Expertise über den Ist-Zustand der Anlage verlangt habe, sei eine Expertise nicht angeordnet worden, was ebenso willkürlich sei. Auch dieses Argument ist unbehelflich, da nicht anzunehmen ist, dass ein Experte im Nachhinein hätte feststellen können, welche Leistung die Anlage erbracht hat. Auch er hätte sich, wie die Vorinstanzen, auf die Zeiterfassungsblätter der Beschwerdegegnerin abstützen müssen. Da die Beschwerdeführerin mit ihrer Sachverhaltsrüge demzufolge nicht durchzudringen vermag, bleibt es bei der von der Vorinstanz resp. dem Zivilgericht festgestellten tatsächlichen Leistung der Maschinenanlage von 52 Flacons pro Minute.
7.5 Somit steht fest, dass die Maschinenanlage eine Leistung von 52 Flacons pro Minute erbracht hat, obwohl eine solche von 180 Flacons pro Minute zwischen den Parteien vertraglich vereinbart worden war. Daraus ergibt sich, dass eine wesentliche Vertragsverletzung im Sinne von Art. 25 CISG vorliegt. Die Vorinstanz hat Art. 25 CISG nicht verletzt, indem sie bei einer Leistung von 52 Flacons pro Minute gegenüber den vereinbarten 180 Flacons pro Minute die Wesentlichkeit bejahte. Die gelieferte Maschinenanlage erbrachte lediglich 29 % der vereinbarten Leistung. Bei einer Produktionseinbusse von 71 % entgeht der Beschwerdegegnerin objektiv gesehen im Wesentlichen, was sie nach dem Vertrag hätte erwarten dürfen. Dies stellt einen Mangel von erheblichem Gewicht dar. Wie die unzähligen Nachbesserungsversuche der Beschwerdeführerin zeigen, konnte er nicht in angemessener Frist behoben werden. Zudem wurde die Abfüll- und Verpackungsanlage speziell auf die Bedürfnisse der Beschwerdegegnerin zugeschnitten konzipiert und ist der Beschwerdegegnerin ein Weiterverkauf der Maschinenanlage unmöglich resp. unzumutbar. Selbst die Beschwerdeführerin geht bei einer Produktionsleistung der Maschinenanlage von 52 Flacons pro Minute von einer wesentlichen Vertragsverletzung aus. Sie macht lediglich geltend, dass die Wesentlichkeit bei 115 Flacons pro Minute zu verneinen wäre. Gegen die entsprechende Erwägung der Vorinstanz resp. des Zivilgerichts, wonach ein Durchsatz von 52 Flacons pro Minute gegenüber den vereinbarten 180 Flacons pro Minute eine Produktionseinbusse von 71 % bedeute und somit die Vertragsverletzung wesentlich sei, bringt sie demgegenüber zu Recht nichts vor.
8. Die Beschwerdeführerin rügt weiter, die Beschwerdegegnerin habe die Aufhebung des Vertrags mit Erklärung vom 23. März 2003 nicht innerhalb angemessener Frist erklärt. Indem die Vorinstanz eine Verwirkung des Aufhebungsrechts wegen "Verfristung" verneinte, habe sie Art. 49 Abs. 2 lit. b CISG verletzt.
8.1 Der Käufer verliert nach Art. 39 Abs. 1 CISG das Recht, sich auf eine Vertragswidrigkeit der Ware zu berufen, wenn er sie dem Verkäufer nicht innerhalb einer angemessenen Frist nach dem Zeitpunkt, in dem er sie festgestellt hat oder hätte feststellen müssen, anzeigt und dabei die Art der Vertragswidrigkeit genau bezeichnet. Nach Art. 39 Abs. 2 CISG verliert der Käufer in jedem Fall das Recht, sich auf die Vertragswidrigkeit der Ware zu berufen, wenn er sie nicht spätestens innerhalb von zwei Jahren, nachdem ihm die Ware tatsächlich übergeben worden ist, dem Verkäufer anzeigt, es sei denn, dass diese Frist mit einer vertraglichen Garantiefrist unvereinbar ist.
Das Recht, die Aufhebung des Vertrags zu erklären, verliert der Käufer nach Art. 49 Abs. 2 lit. b i CISG, wenn er im Falle einer anderen Vertragsverletzung als verspäteter Lieferung die Aufhebung nicht innerhalb einer angemessenen Frist erklärt, nachdem er die Vertragsverletzung kannte oder kennen musste. Die Frage, welche Frist als angemessen im Sinne von Art. 49 Abs. 2 lit. b CISG gilt, beurteilt sich nach den Umständen des Einzelfalls und dem Zweck der Vorschrift von Art. 49 Abs. 2 lit. b CISG. In die Beurteilung einzubeziehen sind unter anderem die Art der Ware und des Mangels sowie das Verhalten des Verkäufers nach erfolgter Mängelrüge (MÜLLER-CHEN, in: SCHLECHTRIEM/SCHWENZER, Kommentar zum Einheitlichen UN-Kaufrecht, 5. Aufl. 2008, N. 31 zu Art. 49 CISG). Die Frist beginnt gemäss Art. 49 Abs. 2 lit. b i CISG zu laufen, wenn der Käufer die Vertragsverletzung kennt oder kennen muss. Zur Kenntnis gehört, dass sich der Käufer über Tatsache, Umfang und Tragweite der Vertragsverletzung im Klaren ist. Erst dann kann er beurteilen, ob eine wesentliche Vertragsverletzung vorliegt, die eine Aufhebung des Vertrags gemäss Art. 49 Abs. 1 lit. a CISG rechtfertigt (MÜLLER-CHEN, a.a.O., N. 34 zu Art. 49 CISG). Grundsätzlich kann ein Zeitraum von ein bis zwei Monaten für die notwendigen Abklärungen als angemessen qualifiziert werden, soweit keine Umstände vorliegen, die eine Verlängerung oder Verkürzung dieses Zeitraums sachlich rechtfertigen (vgl. BRUNNER, a.a.O., N. 12 zu Art. 49 CISG; MÜLLER-CHEN, a.a.O., N. 32 FN. 114 zu Art. 49 CISG).
8.2 Die Vorinstanz schützte die Ausführungen des Zivilgerichts, wonach die Beschwerdegegnerin die Aufhebung des Vertrags innerhalb angemessener Frist erklärt habe. Das Zivilgericht hielt fest, der Mangel sei nach Art. 39 Abs. 1 CISG rechtzeitig gerügt worden. Die Beschwerdegegnerin habe die Mängel der installierten Anlage umgehend gerügt, nachdem die Installation beendet und die ersten Probeläufe abgeschlossen gewesen seien, so erstmals am 5. Oktober 2001. Aus der daraufhin folgenden Korrespondenz zwischen den Parteien gehe hervor, dass die Beschwerdeführerin an der Anlage laufend Nachbesserungsversuche vorgenommen habe. Die Beschwerdegegnerin habe bis im Dezember 2002 über zwanzig Schreiben verfasst, in denen die nach den Nachbesserungsversuchen jeweils weiterhin bestehenden Mängel detailliert dargelegt worden seien. Nachdem die Beschwerdeführerin über ein Jahr lang Nachbesserungsversuche an der Anlage unternommen habe, habe sie mit Schreiben vom 6. Dezember 2002 erstmals erläutert, dass die von der Beschwerdegegnerin verlangte Leistung von 180 Flaschen pro Minute unmöglich sei, und gleichzeitig weitere Verbesserungsvorschläge gemacht. Die Beschwerdegegnerin habe daraufhin mit Schreiben vom 10. Dezember 2002 auf den Schaden hingewiesen, der ihr bis dahin durch die mangelhafte Anlage entstanden sei, und die Beschwerdeführerin aufgefordert, eine Frist zu bestimmen, die sie für die Installation einer korrekt funktionierenden Anlage benötigen würde. Nach einer Besprechung bei der Beschwerdegegnerin habe die Beschwerdeführerin am 14. Februar 2003 einen Kompromissvorschlag gemacht, der jedoch bezüglich Leistung wiederum weit unter dem vertraglich Vereinbarten geblieben sei. Erst zu diesem Zeitpunkt sei klar geworden, dass der Beschwerdegegnerin im Wesentlichen entgehen würde, was sie von der korrekten Erfüllung des Vertrags erwarten durfte. Daher habe zu diesem Zeitpunkt die Frist nach Art. 49 Abs. 2 lit. b CISG zur Vertragsaufhebung zu laufen begonnen. Mit Erklärung der Vertragsaufhebung vom 23. Mai 2003 (recte: 23. März 2003) habe die Beschwerdegegnerin innert angemessener Frist reagiert. Es sei zu berücksichtigen, dass aufgrund der Komplexität des Falles einer Vertragsaufhebung umfangreiche Abklärungen rechtlicher und betriebswirtschaftlicher Natur vorauszugehen hatten und der Beschwerdegegnerin daher die Frist von etwas mehr als zwei Monaten (recte: knapp eineinhalb Monaten) zuzubilligen sei.
8.3 Die Beschwerdeführerin rügt die Feststellung als offensichtlich unrichtig bzw. willkürlich, wonach die Beschwerdegegnerin am 14. Februar 2003 von der wesentlichen Vertragsverletzung Kenntnis erhalten habe. Zur Begründung bringt sie vor, mit Schreiben vom 6. Dezember 2002 habe sie klargestellt, dass mit der Anlage die geforderten 180 Flacons pro Minute unmöglich erreicht werden könnten. Damit sei die Nichterfüllung definitiv festgestanden. Das Zivilgericht habe nicht schliessen dürfen, dass die wesentliche Vertragsverletzung für die Beschwerdegegnerin erst am 14. Februar 2003 deutlich geworden sei. Da sich das Zivilgericht damit in Widerspruch zu seiner eigenen Feststellung hinsichtlich des Schreibens vom 6. Dezember 2002 gesetzt habe, liege eine offensichtlich unrichtige bzw. willkürliche Tatsachenfeststellung vor.
Dieser Argumentation kann nicht gefolgt werden. Die Beschwerdeführerin verkennt, dass mit Schreiben vom 6. Dezember 2002 einzig feststand, dass die vertraglich vereinbarte Leistung von 180 Flacons pro Minute nicht erreicht werden konnte. Welche Leistung die Produktionsanlage durch Nachbesserungsversuche erreichen würde, war zu diesem Zeitpunkt noch nicht klar. Ebenso hatte die Beschwerdegegnerin zu diesem Zeitpunkt noch keine Kenntnisse, ob sich die Vertragsverletzung als wesentlich herausstellen würde. Erst nach der Besprechung und mit der Unterbreitung des Kompromissvorschlages vom 14. Februar 2003 wurde ihr bewusst, dass die Leistung weit unter dem vertraglich Vereinbarten bleiben und somit eine wesentliche Vertragsverletzung vorliegen würde. Die Vorinstanz resp. das Zivilgericht hat nicht widersprüchlich, geschweige denn willkürlich, argumentiert.
8.4 Da die Beschwerdegegnerin somit am 14. Februar 2003 im Sinne von Art. 49 Abs. 2 lit. b i CISG von der wesentlichen Vertragsverletzung Kenntnis erhielt, hat sie ihr Recht zur Vertragsaufhebung nicht verwirkt, indem sie am 23. März 2003 die Aufhebung des Vertrags erklärte. Sie hat ihre Erklärung innerhalb angemessener Frist nach Art. 49 Abs. 2 lit. b CISG abgegeben. Selbst die Beschwerdeführerin erachtet im Übrigen eine Frist von einem bis zwei Monaten grundsätzlich als angemessen.
9. Weiter rügt die Beschwerdeführerin, die Vorinstanz habe Art. 82 Abs. 1 CISG verletzt, indem sie entschieden habe, die Nutzung der Anlage habe nicht zu einem Untergang des Aufhebungsrechts geführt.
9.1 Nach Art. 82 Abs. 1 CISG verliert der Käufer das Recht, die Aufhebung des Vertrags zu erklären, wenn es ihm unmöglich ist, die Ware im Wesentlichen in dem Zustand zurückzugeben, in dem er sie erhalten hat. Dem Käufer steht demzufolge das Vertragsaufhebungsrecht grundsätzlich nur dann zu, wenn er die Ware unversehrt zurückgeben kann. Dieser Grundsatz der unversehrten Rückgewähr wird aber in zweifacher Weise erheblich eingeschränkt. Art. 82 Abs. 1 CISG enthält mit dem Hinweis "im Wesentlichen" eine Bagatellklausel, wonach das Aufhebungsrecht nur in Fällen verwirkt, in denen der Zustand der Sache derart verändert ist, dass es unangemessen wäre, vom Verkäufer die Rücknahme zu verlangen (Weber, in: Honsell, Kommentar zum UN-Kaufrecht, 1997, N. 1 f. zu Art. 82 CISG; Hornung/Fountoulakis, in: Schlechtriem/Schwenzer, Kommentar zum Einheitlichen UN-Kaufrecht, 5. Aufl. 2008, N. 6 zu Art. 82 CISG). Bei langlebigen Gütern bringt der Gebrauch in der Regel nur eine unwesentliche Veränderung mit sich (Weber, a.a.O., N. 7 zu Art. 82 CISG). Weiter sind in Art. 82 Abs. 2 CISG verschiedene Ausnahmen vom Grundsatz der unversehrten Rückgewähr aufgeführt. So findet Art. 82 Abs. 1 CISG insbesondere dann keine Anwendung, wenn die Unmöglichkeit, die Ware zurückzugeben oder sie im Wesentlichen in dem Zustand zurückzugeben, in dem der Käufer sie erhalten hat, nicht auf einer Handlung oder Unterlassung des Käufers beruht (Art. 82 Abs. 2 lit. a CISG) oder wenn der Käufer die Ware der normalen Verwendung entsprechend verbraucht oder verändert hat, bevor er die Vertragswidrigkeit entdeckt hat oder hätte entdecken müssen (Art. 82 Abs. 2 lit. c CISG).
9.2 Den vorinstanzlichen Feststellungen lässt sich nicht entnehmen, dass die Beschwerdegegnerin die Maschinenanlage nicht mehr im Wesentlichen in dem Zustand zurückgeben kann, in dem sie diese erhalten hat. Diesbezüglich erhebt die Beschwerdeführerin auch keine Sachverhaltsrüge.
Da somit feststeht, dass die Maschinenanlage im Wesentlichen unversehrt zurückgegeben werden kann, fällt eine Verwirkung des Rechts auf Vertragsaufhebung nach Art. 82 CISG von vornherein ausser Betracht. Die Beschwerdeführerin verkennt dies und stösst mit ihren Vorbringen, wonach die Beschwerdegegnerin durch eine permanente Nutzung ihr Aufhebungsrecht verwirkt haben sollte, ins Leere.
10. Die Beschwerdeführerin rügt schliesslich eine Verletzung von Art. 210 Abs. 1 OR i.V.m. Art. 116 ff. und Art. 148 IPRG. Sie stellt sich auf den Standpunkt, die Ansprüche der Beschwerdegegnerin seien entgegen der Ansicht der Vorinstanz verjährt. Auf den vorliegenden Fall finde die einjährige Verjährungsfrist nach Art. 210 OR Anwendung.
10.1 Die Verjährung von Ansprüchen aus internationalen Warenverträgen wird durch das CISG nicht geregelt (Brunner, a.a.O., N. 18 zu Art. 4 CISG; Dasser, in: Basler Kommentar, Internationales Privatrecht, 2. Aufl. 2007, N. 3 zu Art. 148 IPRG; Ferrari, in: Schlechtriem/Schwenzer, Kommentar zum Einheitlichen UN-Kaufrecht, 5. Aufl. 2008, N. 35 zu Art. 4 CISG; Honsell, Schweizerisches Obligationenrecht, Besonderer Teil, 8. Aufl. 2006, S. 154; Keller/Girsberger, in: Zürcher Kommentar zum IPRG, 2. Aufl. 2004, N. 7 zu Art. 148 IPRG; Siehr, in: Honsell, Kommentar zum UN-Kaufrecht, 1997, N. 23 zu Art. 4 CISG; Staudinger/Magnus, a.a.O., N. 38 zu Art. 4 CISG). Ob ein geltend gemachter Anspruch aus einem dem CISG unterstehenden Kaufvertrag verjährt ist, muss somit nach dem gestützt auf das Kollisionsrecht des Forumstaats ermittelten nationalen Recht beantwortet werden. Verweist das Kollisionsrecht des Forumstaats auf das materielle Recht eines Vertragsstaats des New Yorker UN-Übereinkommens vom 14. Juni 1974 über die Verjährung beim internationalen Warenkauf, so beurteilt sich die Verjährung nach diesem Übereinkommen (Brunner, a.a.O., N. 18 zu Art. 4 CISG; Koller, Die Verjährung von Ansprüchen des Käufers aus der Lieferung nicht vertragskonformer Ware im Spannungsfeld zwischen UN-Kaufrecht [CISG] und nationalem Partikularrecht, recht 2003, S. 42).
10.2 Aufgrund des gewöhnlichen Aufenthalts der Beschwerdeführerin als Verkäuferin in der Schweiz hat die Vorinstanz zu Recht erkannt, die Frage der Verjährung des Rechts zur Vertragsaufhebung richte sich nach schweizerischem Recht (Art. 118 i.V.m. Art. 148 IPRG i.V.m. Art. 3 des Haager Übereinkommens vom 15. Juni 1955 betreffend das auf internationale Kaufverträge über bewegliche körperliche Sachen anzuwendende Recht [SR 0.221.211.4]). Da die Schweiz dem New Yorker UN-Übereinkommen vom 14. Juni 1974 über die Verjährung beim internationalen Warenkauf nicht beigetreten ist, bleibt die nach diesem Übereinkommen für alle Ansprüche aus internationalen Kaufverträgen geltende Verjährungsfrist von vier Jahren ohne Belang. Somit untersteht vorliegend die Frage der Verjährung der Ansprüche aus dem zwischen den Parteien abgeschlossenen Vertrag den Bestimmungen des schweizerischen Obligationenrechts vom 30. März 1911 (OR; SR 220).
10.3 Die Beschwerdeführerin stellt sich auf den Standpunkt, dass sich vorliegend die Verjährung nach Art. 210 OR richte.
Nach Art. 210 OR verjähren die Klagen auf Gewährleistung wegen Mängel der Sache grundsätzlich mit Ablauf eines Jahres nach deren Ablieferung an den Käufer. Die Anwendung der einjährigen Verjährungsfrist von Art. 210 OR auf Verträge, die dem CISG unterliegen, kann unter Umständen zum stossenden Ergebnis führen, dass die Ansprüche infolge Vertragswidrigkeit der Ware bereits verjährt sind, wenn die Rügefrist nach Art. 39 Abs. 2 CISG noch laufen würde. Denn wie bereits vorhergehend ausgeführt, verliert der Käufer nach Art. 39 Abs. 2 CISG das Recht, sich auf die Vertragswidrigkeit der Ware zu berufen, wenn er sie dem Verkäufer nicht spätestens innerhalb von zwei Jahren nach der Warenübergabe anzeigt. In der Lehre wird die Anwendung von Art. 210 OR auf Kaufverträge, die dem CISG unterliegen, denn auch als problematisch erachtet und daher überwiegend abgelehnt (Brunner, a.a.O., N. 25 zu Art. 4 CISG; Dasser, a.a.O., N. 3 zu Art. 148 IPRG; Honsell, a.a.O, S. 154; Keller/Girsberger, a.a.O., N. 7 zu Art. 148 IPRG; Koller, a.a.O., S. 47 f.; Will, Zum Wiener UN-Kaufrecht/Verjährung, SJZ 1998, S. 146 f.). Dem ist beizupflichten. Die einjährige Verjährungsfrist des Art. 210 OR ist jedenfalls insoweit nicht anzuwenden, als dies dazu führen würde, dass die Verjährung vor Eintritt des Ablaufs der zweijährigen Rügefrist von Art. 39 Abs. 2 CISG eintreten und somit zu einem völkerrechtswidrigen Resultat führen würde.
Zur Frage, wie die Regel von Art. 210 OR anzupassen ist, bestehen verschiedene Lösungsansätze (vgl. dazu namentlich Brunner, a.a.O., N. 25 ff. zu Art. 4 CISG; Koller, a.a.O., S. 45 ff.). So wird beispielsweise vertreten, die allgemeine zehnjährige Verjährungsfrist von Art. 127 OR sei massgebend (vgl. Literatur bei Schlechtriem/Schwenzer, N. 29 FN. 141 zu Art. 39 CISG), die Verjährungsfrist von Art. 210 OR sei auf zwei Jahre seit der Ablieferung der Ware auszudehnen (Urteil Cour de Justice de Genève vom 10. Oktober 1997, CISG-online Nr. 295) oder die Einjahresfrist von Art. 210 OR solle nicht schon mit der Ablieferung der Kaufsache, sondern erst mit der Mängelrüge zu laufen beginnen (Urteile des Handelsgerichts des Kantons Bern vom 30. Oktober 2001, CISG-online Nr. 956, und vom 17. Januar 2002, CISG-online Nr. 725).
Vorliegend kann die Frage offengelassen werden, welcher Lösung der Vorzug zu geben ist, namentlich, ob eine zwei- oder eine zehnjährige Verjährungsfrist zur Anwendung gelangen soll. Wie die Vorinstanz zutreffend ausführte, richtet sich die Unterbrechung der Verjährung ebenfalls nach schweizerischem Recht. Nach Art. 135 OR wird die Verjährung sowohl durch Anerkennung der Forderung als auch durch Schuldbetreibung unterbrochen. Als Anerkennung einer Forderung gilt jedes Verhalten des Schuldners, das vom Gläubiger nach Treu und Glauben im Verkehr als Bestätigung der rechtlichen Verpflichtung aufgefasst werden darf (Urteil 4C.60/2002 vom 16. Mai 2002 E. 1.3). Nachdem die Beschwerdegegnerin die Verjährung durch ihren letzten Nachbesserungsversuch vom 31. Oktober 2002 unterbrochen hat (vgl. <ref-ruling> E. 3c S. 272) und die Beschwerdeführerin am 9. Februar 2004 die Betreibung einleitete, wäre die Verjährung selbst bei Annahme einer zweijährigen Frist nicht eingetreten.
10.4 Demzufolge sind die Ansprüche infolge der wesentlichen Vertragswidrigkeit vorliegend nicht verjährt. Da die eingeklagten Ansprüche der Beschwerdegegnerin im Quantitativen nicht bestritten sind, ist davon auszugehen, dass sie von der Vorinstanz zu Recht zugesprochen wurden.
11. Die Beschwerdeführerin rügt schlussendlich, die Vorinstanz habe Art. 84 Abs. 2 CISG und Art. 29 Abs. 2 BV verletzt, indem sie die Verrechnung mit ihrem Nutzungsersatzanspruch wegen fehlender Substantiierung und unzureichendem Beweisangebot abgelehnt habe.
11.1 Ob das Zivilgericht zu Recht erwog, dass die von der Beschwerdeführerin geltend gemachte Nutzungsentschädigung nicht in Betracht käme, da die Schadenminderungspflicht der Beschwerdeführerin nach Art. 77 CISG eine verrechenbare Gegenforderung der Beschwerdeführerin aus Nutzungsentschädigung ausschliesse, liess die Vorinstanz offen. Sie erachtete die Gegenforderung der Beschwerdeführerin als weder genügend substantiiert noch unter Beweis gestellt. Der Antrag auf Feststellung der Nutzungsentschädigung durch eine gerichtliche Expertise genüge nicht zur Substantiierung einer Forderung, welche die Beschwerdeführerin in Kenntnis der Anlage selbst hätte beziffern können. Als Beweis für die unbezifferte Forderung biete die Beschwerdeführerin neben der Expertise nur die Befragung eines eigenen Angestellten als Zeugen an. Abgesehen davon, dass der Mitarbeiter kaum als Zeuge einzuvernehmen wäre, sei der angebotene Beweis untauglich. Zeugen seien Personen, die von einer zu beweisenden Tatsache durch eigene Sinneswahrnehmung Kenntnis hätten. Sie seien aber nicht geeignet, die Substantiierungslast zu übernehmen. Eine verrechenbare Gegenforderung sei daher weder rechtzeitig substantiiert noch tauglich bewiesen worden. Das Zivilgericht habe die widerklageweise geltend gemachte und eventualiter zur Verrechnung gestellte Nutzungsentschädigung zu Recht abgewiesen.
11.2 Die Beschwerdeführerin bringt vor, sie habe den Anspruch auf Nutzungsherausgabe ausreichend substantiiert und taugliche Beweismittel angeboten.
Es trifft zu, dass die Beschwerdeführerin die geltend gemachte Nutzungsentschädigung entgegen den Ausführungen der Vorinstanz in ihrer Klageantwort und Widerklage beziffert hat. So hat sie zunächst zwar ausgeführt, eine angemessene Nutzungsentschädigung sei durch eine gerichtlich anzuordnende Expertise festzustellen. In der Folge hat sie jedoch die geltend gemachte Nutzungsentschädigung für die Dauer von Oktober 2001 bis (vorerst) September 2005 auf EUR 1'997'416.16 beziffert. Sie gab zudem an, bei der Vermietung von Verpackungsmaschinen verrechne sie jeweils eine Mietgebühr von 2.8 % pro Monat bezogen auf den Kaufpreis. Als Zeuge bzw. Auskunftsperson benannte sie A._.
11.3 Es erscheint fraglich, ob die Vorinstanz zu Recht davon ausging, dass die Beschwerdeführerin die geltend gemachte Forderung nicht genügend substantiierte. Jedoch kann der Vorinstanz beigepflichtet werden, dass die Beschwerdeführerin die Forderung nicht genügend unter Beweis stellte. Obwohl sie in ihrer Klageantwort und Widerklage behauptete, üblicherweise werde eine derart hohe Mietgebühr verrechnet, hat sie keine zumutbaren und aussagekräftigen Beweismittel ins Recht gelegt. Sie hat weder Verträge von entsprechenden Mietgeschäften, noch irgendwelche Kalkulationstabellen, Abrechnungen oder Geschäftsbedingungen von Leasinggesellschaften ins Recht gelegt oder etwa einen Branchenvertreter benannt, der eine derartige Übung hätte bezeugen können. Indessen hat sie lediglich einen Mitarbeiter als Zeugen bzw. als Auskunftsperson angerufen und eine Expertise zur Feststellung der Höhe der Nutzungsentschädigung verlangt. Indem die Vorinstanz diese Beweismittel als untauglich erachtete, hat sie Art. 29 Abs. 2 BV nicht verletzt. Denn der Verzicht auf ein angerufenes Beweismittel ist zulässig, wenn es von vornherein nicht geeignet ist, die behaupteten Tatsachen zu beweisen (<ref-ruling> E. 3 S. 157 mit Hinweisen).
12. Die Beschwerde ist aus diesen Gründen abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 20'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 22'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 18. Mai 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Die Gerichtsschreiberin:
Klett Sommer