Sachverhalt:
A. Die A._ AG (Klägerin 1) und die B._ AG (Klägerin 2) sind in Zürich domiziliert, die C._ GmbH (Klägerin 3), die D._ GmbH (Klägerin 4), die E._ GmbH (Klägerin 5) und die F._ AG (Klägerin 6) sind in Deutschland ansässig. Die Klägerinnen stellen das Produkt M. her oder vertreiben es.
Die G._ GmbH (Beklagte) hat ihren Sitz in Deutschland. Sie ist Inhaberin des europäischen Patents X. Sie beansprucht dieses Patent für mehrere Vertragsstaaten.
B. Am 25. Mai 2005 stellten die Klägerinnen beim Handelsgericht des Kantons Zürich folgende Rechtsbegehren:
"1. Der schweizerische Teil des europäischen Patents X. sei nichtig zu erklären,
eventualiter sei gerichtlich festzustellen, dass die Klägerinnen mit dem Produkt M. den schweizerischen Teil des europäischen Patents X. der Beklagten nicht verletzen oder verletzt haben.
1. Es sei gerichtlich festzustellen, dass die Klägerinnen mit dem Produkt M. weder den deutschen noch den französischen Teil des europäischen Patents X. verletzen oder verletzt haben,
insbesondere weil
a) das beklagtische Patent X. ungültig oder nicht durchsetzbar ist; oder
b) das Herstellen, Feilhalten, Vertreiben und in Verkehr bringen des Produktes M. durch die Klägerinnen weder in der Schweiz noch im Ausland das europäische Patent der Beklagten verletzt oder verletzt hat.
2. Es sei gerichtlich festzustellen, dass der Beklagten gegenüber den Klägerinnen keinerlei durchsetzbare Forderungen, insbesondere weder Schadenersatz-, Gewinnherausgabe- oder Genugtuungsansprüche im Zusammenhang mit dem klägerischen Produkt M. oder mit den beklagtischen Patenten oder Patentanteilen zustehen."
C. Die Beklagte schloss auf Nichteintreten bzw. Abweisung der Klage und erhob Widerklage im Wesentlichen mit den Rechtsbegehren, es sei den Klägerinnen 1, 2 und 5 zu verbieten, in der Schweiz bestimmte Produkte, insbesondere die unter Bezeichnung M. vertriebenen, herzustellen, anzubieten, zu verkaufen oder anderweitig in Verkehr zu bringen, in die Schweiz einzuführen sowie aus der Schweiz auszuführen oder zu solchen Handlungen Dritter anzustiften, bei ihnen mitzuwirken oder ihre Begehung zu begünstigen (Ziffer 1), die Klägerinnen 1, 2 und 5 seien für entsprechend patentverletzende Handlungen zur Rechnungslegung (Ziffer 2) sowie zu Schadenersatz oder Gewinnherausgabe (Ziffer 3) zu verpflichten.
Auf Antrag der Beklagten beschränkte das Handelsgericht das Verfahren mit Verfügung vom 30. September 2005 vorerst auf die Frage der örtlichen Zuständigkeit bzw. des Rechtsschutzinteresses.
D. Mit Beschluss vom 3. April 2006 trat das Handelsgericht auf die Klage der Klägerinnen 1 und 2 ein (Ziffer 1a); auf die Klage der Klägerinnen 3, 4 und 6 trat es nicht ein (Ziffer 1b). Auf die Klage der Klägerin 5 wurde bezüglich Rechtsbegehren 1 eingetreten, bezüglich Rechtsbegehren 2 nicht eingetreten und bezüglich Rechtsbegehren 3 insoweit eingetreten, als es um Forderungen aus Verletzung des schweizerischen Teils des Streitpatents geht, und nicht eingetreten insoweit, als es um Forderungen aus Verletzung ausländischer Teile des Streitpatents geht. Das Gericht führte aus, dass das LugÜ zur Anwendung gelangt. Zum Rechtsbegehren 1 stellte das Gericht fest, dass die Klägerinnen 3, 4 und 6 in der Schweiz am Markt nicht aufträten und auch nicht behaupteten, dass sie dies beabsichtigten, weshalb sie kein Rechtsschutzinteresse an der beantragten Feststellung der Patentnichtigkeit hätten. Die örtliche Zuständigkeit zur Beurteilung des Rechtsbegehrens 2 bejahte das Gericht für die Klägerinnen 1 und 2 mit der Begründung, sie hätten ihren Sitz in der Schweiz und <ref-law> schütze nicht den formell, sondern den materiell Beklagten. Die Zuständigkeit nach Art. 5 Ziffer 3 LugÜ verneinte das Gericht mit der Begründung, die Klägerinnen 1 und 2 könnten sich darauf nicht berufen, weil sie ihren Sitz in der Schweiz haben und die Klägerinnen 3-6 nicht, weil die Verletzung ausländischer Patente zur Diskussion stehe. Die Zuständigkeit gestützt auf Art. 6 Ziffer 1 LugÜ, auf die sich die Klägerinnen 3-6 beriefen, verneinte das Gericht. Für das Rechtsbegehren 3 bejahte das Gericht die Zuständigkeit nach Art. 5 Ziffer 3 LugÜ insoweit, als es um die Verletzung des schweizerischen Teils des europäischen Patents geht, wobei es das Feststellungsinteresse nur für die Klägerinnen 1, 2 und 5 bejahte.
E. Gegen den Beschluss des Handelsgerichts des Kantons Zürich vom 3. April 2006 haben sowohl die Beklagte wie die Klägerin 6 eidgenössische Berufung eingereicht. Die Klägerin 6 beantragt dem Bundesgericht, der angefochtene Beschluss sei teilweise, nämlich in Bezug auf sie aufzuheben, die Zuständigkeit sei zu bejahen und die Vorinstanz sei anzuweisen, auf ihre Klage einzutreten (Ziffer 1), eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen (Ziffer 2). Sie rügt, die Vorinstanz habe das LugÜ verletzt, indem sie ein Feststellungsinteresse an der Klärung des Verletzungsvorwurfs verlangt habe, indem sie ihrem Entscheid einen bundesrechtswidrigen Begriff des Feststellungsinteresses zugrundegelegt habe, soweit sie dieses verlangt habe, und sie habe <ref-law> verletzt, soweit sie ihr ohne Beweisverfahren das Interesse abgesprochen habe.
F. Die Beklagte schliesst auf Abweisung der Berufung der Klägerin 6, soweit darauf einzutreten ist.
G. Das Bundesgericht hat die Berufung der Beklagten gutgeheissen und den angefochtenen Beschluss gemäss den Rechtsbegehren der Beklagten in dem Sinne abgeändert, dass auf die Feststellungsbegehren der Klägerinnen 1 und 2 in Bezug auf die Verletzung ausländischer Patente nicht eingetreten wird.

Das Bundesgericht zieht in Erwägung:
1. Die Berufung ist gemäss Art. 48 OG in der Regel erst gegen die Endentscheide der oberen kantonalen Gerichte zulässig.
1.1 Ein Endentscheid im Sinn dieser Bestimmung liegt nach der Rechtsprechung nur vor, wenn das kantonale Gericht über den im Streit stehenden Anspruch materiell entschieden oder dessen Beurteilung aus einem Grund abgelehnt hat, der endgültig verbietet, dass derselbe Anspruch nochmals geltend gemacht wird, weshalb er insoweit materiell rechtskräftig wird (<ref-ruling> E. 1a S. 476 mit zahlreichen Verweisen). Im vorliegenden Fall ist das Handelsgericht auf die Klage der Klägerin 6 mit der Begründung nicht eingetreten, es fehle das Rechtsschutz- bzw. Feststellungsinteresse (Rechtsbegehren 1 und Rechtsbegehren 3 mit Bezug auf den schweizerischen Teil des europäischen Patents) bzw. die örtliche Zuständigkeit sei nicht gegeben (Rechtsbegehren 2 und Rechtsbegehren 3 betreffend ausländische Patente). Das Gericht hat damit die Beurteilung der Klagebegehren aus Gründen verweigert, die der Klägerin endgültig verbieten, denselben Anspruch vor schweizerischen Gerichten nochmals geltend zu machen (vgl. dazu Jean-François Poudret, Commentaire de la loi fédérale d'organisation judiciaire du 16 décembre 1943, N. 1.1.4.2 zu Art. 48 OG; Georg Messmer/Hermann Imboden, Die eidgenössischen Rechtsmittel in Zivilsachen, Nr. 66). Damit sind die Voraussetzungen von Art. 48 OG gegeben.
1.2 Das Handelsgericht ist auf die Rechtsbegehren der Klägerin 6 vollumfänglich nicht eingetreten, hat seine Zuständigkeit zur Beurteilung der Begehren der Klägerinnen 1, 2 und 5 jedoch mindestens teilweise bejaht. Insofern bleibt das Verfahren hängig. Beim angefochtenen Entscheid handelt es sich daher um einen Teilentscheid, denn es ist nur über einen Teil der subjektiv (und objektiv) gehäuften Klagen durch das Nichteintreten entschieden worden. Teilentscheide sind nach der Praxis mit Berufung selbständig anfechtbar, wenn die davon erfassten Begehren zum Gegenstand eines gesonderten Prozesses hätten gemacht werden können und deren Beurteilung für den Entscheid über die übrigen Begehren präjudiziell ist (<ref-ruling> E. 1a S. 409 mit Hinweisen) oder wenn der Umfang des Beweisverfahrens in erheblichem Mass davon abhängt, ob das Verfahren gegen alle oder nur einen Teil der Beklagten durchgeführt wird (<ref-ruling> E. 1.1 S. 27).
1.3 Die Klägerin 6 hätte die Rechtsbegehren 1 bis 3 zum Gegenstand eines gesonderten Prozesses machen können, und der Grund der Prozessökonomie, welcher eine gesonderte Anrufung des Bundesgerichts gegen Teilurteile rechtfertigt, kann vorliegend ohne weiteres als gegeben angesehen werden. Denn es ist zu beachten, dass auf die Begehren der Klägerin 6 im Rahmen eines selbständigen Vorentscheides über die Zuständigkeit der Vorinstanz zur Beurteilung der objektiv und subjektiv gehäuften Klagen nicht eingetreten wurde und grundsätzlich aus Gründen der Prozessökonomie ein Interesse an der vorgängigen Beurteilung der Prozessvoraussetzungen besteht, dem insbesondere in Art. 49 OG Rechnung getragen wird.
2. In Rechtsbegehren 2 beantragt die Klägerin die Feststellung der Nichtverletzung ausländischer Streitpatente und in Rechtsbegehren 3 dementsprechend die Feststellung, dass der Beklagten daraus keine Forderungen zustehen.
2.1 Die Klägerin 6 hat im kantonalen Verfahren die Zuständigkeit der Vorinstanz zur Beurteilung des Klagebegehrens 2 unter anderem auf Art. 6 Ziffer 1 LugÜ gestützt und hält in der Berufung daran fest. Nach dieser Bestimmung kann eine Person, die ihren Wohnsitz in dem Hoheitsgebiet eines Vertragsstaats hat, auch vor dem Gericht verklagt werden, in dessen Bezirk einer der Beklagten seinen Wohnsitz hat, wenn mehrere Personen zusammen verklagt werden. Die Klägerin 6 möchte diese Bestimmung für negative Feststellungsklagen entsprechend auf die aktive Streitgenossenschaft anwenden. Nachdem die Berufung der Beklagten gegen die Klägerinnen 1 und 2 gutgeheissen und auf deren Klagebegehren 2 sowie den entsprechenden Teil der Klagebegehren 3 nicht eingetreten worden ist, sind neben der Klägerin 6 keine Parteien mehr vorhanden, auf deren entsprechendes Klagebegehren 2 eingetreten werden könnte und die somit im Sinne der Auslegung der Klägerin 6 zusammen "verklagt" werden könnten. Der Zuständigkeit nach Art. 6 Ziffer 1 LugÜ fehlt damit die Grundlage. Die Vorinstanz hat ihre Zuständigkeit nach dieser Bestimmung zu Recht verneint.
2.2 Die Klägerin 6 hält in ihrer Berufung sodann daran fest, dass der Gerichtsstand am Ort der deliktischen Handlung gemäss Art. 5 Ziffer 3 LugÜ die Zuständigkeit der Vorinstanz zur Beurteilung der (Nicht-)Verletzung ausländischer Patente der Beklagten begründe. Nach Art. 5 Ziffer 3 LugÜ kann eine Person mit Wohnsitz in einem Vertragsstaat in einem anderen Vertragsstaat vor dem Gericht des Ortes verklagt werden, an dem das schädigende Ereignis eingetreten ist, wenn eine unerlaubte bzw. dieser gleichgestellte Handlung oder Ansprüche aus einer solchen Handlung den Gegenstand des Verfahrens bilden. Diese Zuständigkeit beruht auf der Erwägung, dass hier eine besondere Nähe zum Streitgegenstand besteht und das Gericht am Ort, an dem das schädigende Ereignis eingetreten ist, am besten in der Lage ist, die erforderlichen Beweise zu erheben und den Streit zu entscheiden (Jan Kropholler, Europäisches Zivilprozessrecht, Kommentar zu EuGVO, Lugano-Übereinkommen und Europäischem Vollstreckungstitel, 8. Aufl. 2005, N. 73 zu Art. 5 EuGVO; Hélène Gaudemet-Tallon, Compétences et exécution des jugements en Europe, 3. Aufl. 2002, S. 125 Rz. 171). Als eingetreten wird das schädigende Ereignis nach der hier massgebenden Praxis des EuGH sowohl am Ort der Vornahme der deliktischen Handlung wie am Ort des Erfolgs anerkannt (<ref-ruling> E. 4a S. 348; Gaudemet-Tallon, a.a.O., S. 172, Rz. 215). Für die Verletzung ausländischer Patente käme höchstens der Handlungsort als Deliktsort in Betracht. Da eine Patentverletzung eine Benutzungshandlung auf dem Gebiet des Staates, für den das Patent erteilt wurde, voraussetzt, kann nämlich der Erfolgsort als Ort, an dem die Rechtsgutverletzung eintritt, immer nur in diesem Staat liegen. Gegen die Zuständigkeit der Gerichte am Handlungsort bei der Verletzung ausländischer Patente im Inland spricht jedoch die Erwägung, dass die Patentverletzung weder im Gerichtsstaat erfolgt ist noch dessen materielles Recht zur Anwendung kommt, womit es an der für Art. 5 Ziffer 3 LugÜ erforderlichen besonderen Nähe zum Streitgegenstand fehlt (Klaus Grabinski, Zur Bedeutung des Europäischen Gerichtsstands- und Vollstreckungsübereinkommens (Brüsseler Übereinkommens) und des Lugano-Übereinkommens in Rechtsstreitigkeiten über Patentverletzungen, in GRUR Int. 2001 S. 201/204 f.; vgl. auch Pierre Véron, Trente ans d'application de la Convention de Bruxelles à l'action en contrefaçon de brevet d'invention, in Journal du Droit International (Clunet) 2001, S. 805/826 f.) Die Vorinstanz hat zutreffend eine Zuständigkeit gestützt auf Art. 5 Ziffer 3 LugÜ für die Feststellung der (Nicht-)Verletzung ausländischer Patente abgelehnt.
2.3 Die Berufung ist unbegründet, soweit sie sich gegen den Entscheid der Vorinstanz richtet, es werde auf das Rechtsbegehren 2 sowie das Rechtsbegehren 3 betreffend ausländische Patente der Klägerin 6 nicht eingetreten.
3. Das Handelsgericht ist im angefochtenen Entscheid auf die Begehren 1 und 3 der Klägerin 6 in der Erwägung nicht eingetreten, der Klägerin fehle das Rechtsschutzinteresse.
3.1 Unter welchen Voraussetzungen die gerichtliche Feststellung des Bestehens oder Nichtbestehens bundesrechtlicher Ansprüche verlangt werden kann, ist nach der Rechtsprechung des Bundesgerichts eine Frage des Bundesrechts. Die Feststellungsklage ist danach insbesondere zuzulassen, wenn die Rechtsbeziehungen der Parteien ungewiss sind, die Ungewissheit durch die Feststellung über Bestand und Inhalt des Rechtsverhältnisses beseitigt werden kann und ihre Fortdauer der Klagepartei nicht zugemutet werden kann, weil sie sie in ihrer Bewegungsfreiheit behindert (<ref-ruling> E. 3.5 S. 324 f.; <ref-ruling> E. 7b S. 429, je mit Verweisen). Inwiefern die Klägerin aus <ref-ruling> E. 2.3 S. 299 f. ableiten will, diese Rechtsprechung sei im Anwendungsbereich des LugÜ überholt, ist nicht nachvollziehbar. Die Vorinstanz hat für die Feststellung, es sei der schweizerische Teil des europäischen Patents der Beklagten nicht verletzt (Begehren 1) und der Beklagten ständen folglich keine Forderungen gegen die Klägerin 6 aus diesem Rechtsgrund zu (Begehren 3), zutreffend ein Feststellungsinteresse im Sinne der Praxis des Bundesgerichts verlangt.
3.2 Nach den Feststellungen der Vorinstanz tritt die Klägerin 6 in der Schweiz nicht am Markt auf und macht auch nicht geltend, dies zu beabsichtigen. Sie wird ausserdem von der Beklagten keiner Patentverletzung in der Schweiz bezichtigt. Von diesen Sachverhaltsfeststellungen ist auszugehen. Denn soweit die Klägerin 6 diese Feststellung unter Berufung auf <ref-law> beanstandet, ist ihren Vorbringen nicht zu entnehmen, dass sie im kantonalen Verfahren einschlägige Beweisanträge gestellt hätte. Die Vorinstanz ist entgegen der Ansicht der Klägerin von einem zutreffenden Begriff des Feststellungsinteresses ausgegangen, als sie verlangte, dass die Klägerin ein eigenes, mindestens tatsächliches Interesse an der begehrten Feststellung nachweisen müsse. Dass sie mit den übrigen Klägerinnen konzernmässig verbunden ist, genügt dafür jedenfalls nicht. Dass ein Verfahren in Deutschland gegen die Klägerin 6 wegen angeblicher Mitverantwortung für Handlungen ihrer Tochtergesellschaften bereits hängig ist, spricht gegen das Feststellungsinteresse der Klägerin 6. Dass Zürich das Zentrum des weltweiten Vertriebs des angeblich patentverletzenden Produkts M. bildet, begründet jedenfalls entgegen der Auffassung der Klägerin 6 nicht ohne weiteres ein Rechtsschutzinteresse der Muttergesellschaft des Konzerns. Schliesslich kann der Klägerin 6 auch darin nicht gefolgt werden, dass angebliche Anschwärzungen durch Dritte ohne weiteres ihr Interesse an den beantragten Feststellungen begründen sollten.
4. Die Berufung der Klägerin 6 gegen den Nichteintretensentscheid des Handelsgerichts Zürich ist abzuweisen. Diesem Verfahrensausgang entsprechend sind die Kosten der Klägerin zu auferlegen.

Demnach erkennt das Bundesgericht:
1. Die Berufung wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 10'000.-- wird der Klägerin 6 auferlegt.
3. Die Klägerin 6 hat die Beklagte für das bundesgerichtliche Verfahren mit Fr. 12'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 23. Oktober 2006
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: