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. 2. 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. 3. 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." 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 der 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), und 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. C. 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 Art. 2 LugÜ 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. Aus Art. 2 LugÜ bejahte das Gericht die örtliche Zuständigkeit für die Klägerinnen 1 und 2 sowohl für Ansprüche aus Verletzung des schweizerischen als auch aus Verletzung ausländischer Teile des Streitpatents. D. Gegen den Beschluss des Handelsgerichts des Kantons Zürich vom 3. April 2006 haben sowohl die Beklagte wie die Klägerin 6 Berufung eingereicht. Die Beklagte stellt den Antrag, es sei Dispositiv-Ziffer 1a) des angefochtenen Entscheides aufzuheben und auf die Klage der Klägerinnen 1 und 2 bezüglich Rechtsbegehren 1 einzutreten, bezüglich Rechtsbegehren 2 nicht einzutreten und bezüglich Rechtsbegehren 3 insoweit einzutreten, als es um Forderungen aus Verletzung des schweizerischen Teils des Streitpatents geht, und nicht einzutreten insoweit, als es um Forderungen aus Verletzung ausländischer Teile des Streitpatents geht. Sie rügt, die Vorinstanz habe den Gerichtsstand für die Verletzung des deutschen und französischen Teils des Patents X. der Beklagten zu Unrecht bejaht. E. Die Klägerinnen 1 und 2 beantragen die Abweisung der Berufung der Beklagten, soweit darauf einzutreten ist.