Sachverhalt:
A. Die X._ GmbH und die YQ._ GmbH (Beschwerdeführerinnen 1 und 2) sowie die YZ._ AG (Beschwerdegegnerin) gehören alle drei der Y._-Gruppe an. Sie sind durch diese Konzernzugehörigkeit verbunden, ohne dass allerdings ein Beherrschungsverhältnis zwischen ihnen vorliegt. Die Beschwerdeführerinnen 1 und 2, beide ansässig in Deutschland, sind Töchter der R._ GmbH, mithin Schwester-Gesellschaften. Die Beschwerdegegnerin war zunächst die YS._ AG die während des erstinstanzlichen Verfahrens von der Muttergesellschaft, der YZ._ AG - der nunmehrigen Beschwerdegegnerin - übernommen wurde und dadurch unterging. Die R._ GmbH und die Beschwerdegegnerin werden (über die YT._ Ltd.) von der YU._ Holding AG beherrscht. Konzernobergesellschaft ist die Gesellschaft YV._ International Corporation.
Die Beschwerdeführerin 1 war im prozessrelevanten Zeitraum (1. März 1998 bis 28. Oktober 2003) als Handelsvertreterin der YS._ AG, d.h. der Rechtsvorgängerin der Beschwerdegegnerin, tätig. Sie vermittelte Kaufverträge über Tintenpatronen zwischen der Beschwerdegegnerin und deutschen Kunden, wobei der Vertrag direkt zwischen der Beschwerdegegnerin und dem Kunden zustande kam. Die Beschwerdeführerin 2 erbrachte für die Beschwerdegegnerin Logistikdienstleistungen. Die Beschwerdegegnerin liess die zu lagernden Produkte zunächst an die Beschwerdeführerin 2 liefern, welche diese zwischenlagerte, den Bestellungen entsprechend zusammenstellte, verpackte und durch konzernunabhängige Frachtführer ausliefern liess. Zur Abwicklung der Verträge und insbesondere zum Zugang zu den damit zusammenhängenden Informationen kann im Einzelnen auf die Erwägungen 1.4 und 1.5 des obergerichtlichen Urteils verwiesen werden.
A._ (Beschwerdeführer 3) und B._ (Beschwerdeführer 4) sind ehemalige Geschäftsführer der Beschwerdeführerin 1. C._ (Beschwerdeführer 5) ist ehemaliger Geschäftsführer der Beschwerdeführerin 2.
Dem vorliegenden Verfahren ging in Deutschland ein Gebrauchsmusterprozess im Zusammenhang mit Tintenpatronen voraus, den die W._ Corporation gegen die Beschwerdeführer angestrengt hat. Mit Urteil des Landgerichts Düsseldorf vom 28. Oktober 2003 wurde eine Gebrauchsmusterverletzung festgestellt. Zugleich wurden die Beschwerdeführer verpflichtet, ihrer Rechnungslegungspflicht gegenüber W._ nachzukommen, um diese in die Lage zu versetzen, den ihr zustehenden Entschädigungs- und Schadenersatzanspruch zu beziffern.
Im anschliessenden Zwangsvollstreckungsbeschluss desselben Gerichts vom 16. Oktober 2006 wurden die Beschwerdeführer 1-3 entsprechend den Vorgaben des Urteils vom 28. Oktober 2003 erneut zur Rechnungslegung verpflichtet, unter Androhung eines Zwangsgeldes von je EUR 15'000.--, ersatzweise eines Tages Zwangshaft je EUR 1'000.-- für den Fall der Nichtbefolgung. Die Beschwerdeführer 1-3 machten geltend, der Rechnungslegungspflicht nicht nachkommen zu können, weil sich die erforderlichen Unterlagen nicht in ihrem Besitz, sondern in dem der Beschwerdegegnerin befänden. Deshalb wurde ihnen die Möglichkeit eingeräumt, die Betreibung des Zwangsgeldes abzuwenden, sofern sie innert sechs Wochen die Beschwerdegegnerin gerichtlich auf Erteilung der Auskünfte in Anspruch nähmen, die sie zur Erfüllung ihrer Rechnungslegungspflicht benötigten. Dieser Beschluss wurde mit Entscheid des Oberlandsgerichts Düsseldorf vom 31. Juli 2008 bezüglich der Beschwerdeführer 1-3 bestätigt und auf die Beschwerdeführer 4 und 5 ausgedehnt. Die dagegen erhobenen Rechtsbeschwerden wies der Bundesgerichtshof mit Beschluss vom 18. Dezember 2008 ab. Gleichzeitig legte er fest, dass die Frist, die den Beschwerdeführern zur Inanspruchnahme der Beschwerdegegnerin offen stehe, drei Wochen nach Zustellung des Beschlusses ende. Mit Urteil des deutschen Bundesgerichtshofes vom 20. Mai 2008 wurde zudem das vorerwähnte Urteil des Landgerichts Düsseldorf vom 28. Oktober 2003 rechtskräftig.
B. Am 3. Juli 2009 erhoben die Beschwerdeführer 1-3 bzw. am 30. November 2009 die Beschwerdeführer 4 und 5 beim Bezirksgericht Uster Klagen mit identischen Rechtsbegehren. Sie verlangten Auskunft, eventualiter Edition von Akten, subeventualiter Einsicht in die Akten hinsichtlich der von ihnen im Zeitraum vom 1. März 1998 bis 28. Oktober 2003 vermittelten bzw. ausgelieferten Tintenpatronentypen. Das Bezirksgericht vereinigte die beiden Prozesse. Mit Beschluss vom 13. Januar 2012 trat es auf die Klage nicht ein, soweit sie von den Beschwerdeführern 1-3 betreffend den Zeitraum vom 14. April 2001 bis 30. September 2002 erhoben wurde, da insoweit eine abgeurteilte Sache vorliege. Im Übrigen wies es die Klage mit Urteil vom gleichen Tag ab, soweit es darauf eintrat. Diesbezüglich bejahte es zwar die eingeklagten Auskunftsansprüche gestützt auf ungeschriebene vertragliche Nebenpflichten bzw. den Grundsatz von Treu und Glauben (§ 242 und 241 Abs. 2 BGB), schützte aber die von der Beschwerdegegnerin erhobene Verjährungseinrede. Es kam zum Schluss, die Verjährungsfrist für die eingeklagten Rechnungslegungsansprüche habe spätestens am 31. Dezember 2003 um 24 Uhr zu laufen begonnen und am 31. Dezember 2006 um 24 Uhr geendet, weshalb die Ansprüche im Zeitpunkt der Einreichung der Klage verjährt gewesen seien.
Eine von den Beschwerdeführern gegen diese Entscheide erhobene Berufung wies das Obergericht des Kantons Zürich mit Urteil vom 25. Juni 2012 unter Bestätigung der angefochtenen Entscheide ab.
C. Die Beschwerdeführer beantragen mit Beschwerde in Zivilsachen, dieses Urteil aufzuheben und die Klage gutzuheissen.
Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde. Die Vorinstanz verzichtete auf eine Vernehmlassung.

Erwägungen:
1. Das angefochtene Urteil des Obergerichts ist ein verfahrensabschliessender Endentscheid (<ref-law>) einer letzten kantonalen Instanz im Sinne von Art. 75 Abs. 1 und 2 BGG. Sodann übersteigt der Streitwert der Begehren aller Beschwerdeführer zusammen (<ref-law>) die Grenze nach <ref-law>. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde - unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 und <ref-law>) - einzutreten.
2. Strittig ist im bundesgerichtlichen Verfahren zum einen, ob die Vorinstanz hinsichtlich der von den Beschwerdeführern 1-3 betreffend den Zeitraum vom 14. April 2001 bis 30. September 2002 eingeklagten Ansprüche zu Recht das Vorliegen einer abgeurteilten Sache bejahte. Zum anderen rügen die Beschwerdeführer eine willkürliche Anwendung des deutschen Rechts betreffend die Verjährung.
Die von der Vorinstanz bejahte Verjährung beschlägt alle Ansprüche, die von den Beschwerdeführern eingeklagt wurden, und damit auch die Auskunftsansprüche, die den Zeitraum vom 14. April 2001 bis 30. September 2002 betreffen, hinsichtlich der die Vorinstanz eine abgeurteilte Sache bejahte. Vermag damit die Begründung, die Ansprüche seien verjährt, die Klageabweisung insgesamt, also auch hinsichtlich der Ansprüche betreffend den Zeitraum vom 14. April 2001 bis 30. September 2002, zu stützen, ist zunächst die Verjährungsfrage zu prüfen.
3. Da die Beschwerdeführer 1-3 ihren Sitz bzw. Wohnsitz in Deutschland haben, liegt ein internationaler Sachverhalt vor. Die hier strittige Verjährungsfrage beurteilt sich nach den zutreffenden und unbestrittenen vorinstanzlichen Ausführungen nach deutschem Recht als dem Recht, das auf die Verträge anwendbar ist, aus denen die streitgegenständlichen Auskunftsansprüche abgeleitet werden (Art. 117 Abs. 2 und 3 sowie <ref-law>; vgl. dazu <ref-ruling> E. 3.2; <ref-ruling> E. 2b).
3.1 In nicht vermögensrechtlichen Streitigkeiten kann mit Beschwerde in Zivilsachen gerügt werden, das nach dem schweizerischen internationalen Privatrecht massgebende ausländische Recht sei nicht richtig angewendet worden (<ref-law>). In vermögensrechtlichen Zivilrechtsstreitigkeiten, wie vorliegend eine gegeben ist, kann die Rüge unrichtiger Anwendung ausländischen Rechts nicht erhoben werden. In diesen Streitigkeiten verbleibt nur die Rüge, der angefochtene Entscheid wende ausländisches Recht willkürlich an (<ref-ruling> E. 3.1; vgl. auch <ref-ruling> E. 4.1.3 S. 616).
3.2 Nach ständiger Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 mit Hinweisen).
Macht die beschwerdeführende Partei eine Verletzung des Willkürverbots von <ref-law> geltend, genügt es nicht, wenn sie einfach behauptet, der angefochtene Entscheid sei willkürlich. Sie hat vielmehr anhand der Erwägungen des angefochtenen Urteils im Einzelnen aufzuzeigen, inwiefern dieser offensichtlich unhaltbar ist (<ref-law>; <ref-ruling> E. 3 S. 352).
4. Die Beschwerdeführer stellen nicht in Frage, dass vorliegend eine dreijährige Verjährungsfrist nach § 195 BGB anwendbar ist. Bestritten wird von ihnen in verjährungsrechtlicher Hinsicht einzig, dass die Verjährungsfrist am 28. Oktober 2003 bzw. am 31. Dezember 2003 zu laufen begonnen habe. Sie rügen, die Vorinstanz sei unter willkürlicher Anwendung von § 199 Abs. 1 BGB zu diesem Schluss gekommen.
Nach § 199 Abs. 1 BGB beginnt die regelmässige Verjährungsfrist mit dem Schluss des Jahres, in dem (1.) der Anspruch entstanden ist und (2.) der Gläubiger von den den Anspruch begründenden Umständen und der Person des Schuldners Kenntnis erlangt oder ohne grobe Fahrlässigkeit erlangen müsste. Die Beschwerdeführer machen geltend, die Vorinstanz habe willkürlich entschieden, dass der auf Treu und Glauben begründete Anspruch auf Auskunft verjährt sei, bevor er überhaupt entstanden sei.
4.1 Die Vorinstanz pflichtete den Erwägungen des Bezirksgerichts bei, nach denen sich die strittigen Informationsansprüche aus ungeschriebenen vertraglichen Nebenpflichten bzw. aus dem Grundsatz von Treu und Glauben ergäben. Die Schaffung einer Gefahr für den Vertragspartner führe nach der deutschen Rechtsprechung zur Nebenpflicht, dahingehend tätig zu werden, dass allfälliger Schaden beim Vertragspartner vermieden werde, was auch dann gelte, wenn der Endabnehmer ein Unternehmen sei und die Gefahr darin bestehe, dass dieser fortlaufende Rechtsansprüche Dritter zu gewärtigen habe. Im vorliegenden Fall ergebe sich eine Pflicht der Beschwerdegegnerin zur Unterstützung der Beschwerdeführer, weil sie die Beschwerdeführerinnen 1 und 2 mit dem Einbezug in ihre Vertriebsstruktur der Gefahr ausgesetzt habe, dass diese Ansprüche Dritter zu gewärtigen hätten. Diese Gefahr habe sich denn auch realisiert, indem die Beschwerdeführerinnen 1 und 2 wegen einer Gebrauchsmusterverletzung zur Schadenersatzleistung und zur Rechnungslegung gegenüber W._ verpflichtet worden seien. Da die Beschwerdeführerinnen aufgrund der von der Beschwerdegegnerin mitzuverantwortenden Archivierungspolitik keinen Zugriff mehr auf die für die Rechnungslegung erforderlichen Daten hätten, seien sie in einer Notlage und habe die Beschwerdegegnerin ihnen beizustehen. Die Beistandspflicht erstrecke sich auch auf die Beschwerdeführer 3-5, die infolge der vertraglichen Beziehungen zwischen der Beschwerdegegnerin und den Beschwerdeführerinnen 1 und 2 in eine eigenpersönliche deliktische Haftung wegen Schutzrechtsverletzung geraten seien.
Hinsichtlich der Entstehung des Auskunftsanspruchs im Sinne von § 199 Abs. 1 Nr. 1 BGB führte die Vorinstanz, wiederum unter teilweiser Verweisung auf die Erwägungen des Bezirksgerichts, aus, ein solcher sei entstanden, sobald er auf dem Klageweg geltend gemacht werden könne, wofür grundsätzlich die Fälligkeit des Anspruchs Voraussetzung sei. Da jede der Beschwerdeführerinnen 1-2 für sich mit der Beschwerdegegnerin in einem Dauerschuldverhältnis gestanden sei, seien fortwährend auch deren Auskunftsansprüche entstanden. Hinsichtlich Begebenheiten, die sich vom 1. März 1998 bis 28. Oktober 2003 ereignet hätten, sei spätestens an diesem zweitgenannten Datum der letzte diesbezügliche Auskunftsanspruch entstanden. Denn mangels anderweitiger Abrede bzw. Umstände hätten die Beschwerdeführer die Informationsleistung sofort verlangen können.
4.2 Die Vorinstanz erachtete es nach diesen Erwägungen für die Entstehung des Auskunftsanspruchs hinreichend, dass die Beschwerdeführer durch Einbezug in das Vertriebssystem der Beschwerdegegnerin der Gefahr von Drittansprüchen ausgesetzt waren und deshalb mangels anderweitiger Abrede jederzeit über die abgewickelten Bestellungen Informationen verlangen konnten, über die sie nicht selber verfügten. Dies umso mehr, als die Gefahr sich mit der gerichtlichen Belangung der Beschwerdeführer wegen Gebrauchsmusterverletzung und erst Recht mit der erstinstanzlichen Verpflichtung durch das Landgericht Düsseldorf vom 28. Oktober 2003 zur Rechnungslegung auch realisiert hatte.
Dies ist ohne weiteres nachvollziehbar und jedenfalls nicht willkürlich. Es erscheint vertretbar, wenn die Vorinstanz es für eine jederzeitige, aus der Vertragstreue fliessende Auskunftspflicht für hinreichend erachtete, dass die Beschwerdeführer der Gefahr ausgesetzt waren, mit Drittansprüchen konfrontiert zu werden und für diesen Fall über die nötigen Daten verfügen mussten, um eine (weitergehende) prozessuale Auseinandersetzung zu vermeiden. In diesem Sinne wäre es, um zum gleichen Ergebnis wie die Vorinstanz zu gelangen, um so mehr vertretbar, die Entstehung einer aus Treu und Glauben fliessenden Pflicht zur Unterstützung der Beschwerdeführer mit den nötigen Daten spätestens in dem Zeitpunkt zu bejahen, in dem die Beschwerdeführer erstinstanzlich zur Rechenschaftsablegung verpflichtet wurden.
4.3 Was die Beschwerdeführer dagegen vorbringen, ist ihre - durchwegs vertretbare - Sicht der Dinge, genügt aber nicht, um die Entscheidung der Vorinstanz als geradezu willkürlich erscheinen zu lassen.
4.3.1 Sie halten dafür, die nach Treu und Glauben abgeleiteten Informationsansprüche hätten erst in dem Zeitpunkt entstehen können, als die Beschwerdeführer rechtskräftig (mit dem Beschluss des Bundesgerichtshofs vom 20. Mai 2008) zur Rechenschaftsablegung verpflichtet wurden.
Es trifft zu, dass sich die Gefahr für die Beschwerdeführer, Ansprüche der W._ gewärtigen zu müssen, nachdem die W._ gegen sie einen Prozess in Deutschland eingeleitet hatte und sie erstinstanzlich verurteilt worden waren, zusätzlich konkretisierte, als der Beschluss des Bundesgerichtshofs erging. Unter Willkürgesichtspunkten erscheint es aber keineswegs als zwingend, die Entstehung der Informationsansprüche entgegen den Erwägungen der Vorinstanz, mit der sich die Beschwerdeführer nicht hinreichend auseinandersetzen, erst damit entstehen zu lassen.
4.3.2 Weiter machen die Beschwerdeführer geltend, die "Gefahr", auf welcher der Anspruch aus Treu und Glauben gründe, habe sich für die Beschwerdeführer nicht schon mit dem rechtskräftigen Urteil im Verfahren betreffend Gebrauchsmusterverletzung realisiert, sondern erst durch die Zwangslage, die aus dem rechtskräftigen Urteil im Zwangsvollstreckungsverfahren (Beschluss vom 18. Dezember 2008) resultiert habe.
Auch diese Argumentation ist unbehelflich. Denn die Vorinstanz erachtete es für die Fälligkeit der Informationsansprüche der Beschwerdeführer nicht erforderlich, dass sich die Gefahr, der die Beschwerdegegnerin die Beschwerdeführer ausgesetzt hatte, (endgültig) realisiert hatte. Weshalb sie damit in Willkür verfallen sein soll, legen die Beschwerdeführer nicht, jedenfalls nicht rechtsgenüglich dar. Wenn sie vorbringen, vor dem rechtskräftigen Urteil im Zwangsvollstreckungsverfahren habe für sie keine "Notwendigkeit" bestanden, gerichtlich gegen die Beschwerdegegnerin vorzugehen, und es sei nicht vertretbar, dies von ihnen zu verlangen, argumentieren sie an der Sache vorbei. Soweit sie damit geltend machen wollen, erst mit dieser Notwendigkeit bzw. mit der Realisierung der Gefahrenlage könnten aus Treu und Glauben Auskunftsansprüche entstehen, legen sie bloss ihre Sicht der Dinge dar, ohne aber Willkür aufzuzeigen.
Nach der vorinstanzlichen Konzeption der Anspruchsentstehung spielt es entgegen den weiteren Vorbringen der Beschwerdeführer auch keine Rolle, dass die Beschwerdegegnerin ihnen in einem Prozess auf Auskunftserteilung ein widersprüchliches Verhalten hätten vorwerfen können, weil sie ja dazumal immer noch (gegenüber der W._) gegen die Auskunftspflicht an sich gerichtlich angekämpft hätten. Denn nach der vorinstanzlichen Konzeption, welche die Beschwerdeführer nicht als willkürlich auszuweisen vermögen, wäre die Beschwerdegegnerin damit nicht durchgedrungen. Die Willkürlichkeit dieser Konzeption ergibt sich namentlich auch nicht daraus, dass sich die Gefahrensituation für die Beschwerdeführer nachträglich hätte entschärfen können, wenn sie in einem der beiden Verfahren in Deutschland obsiegt hätten und damit die Auskunftsansprüche aufgrund veränderter Gegebenheiten allenfalls nachträglich dahingefallen wären.
4.4 Zusammenfassend vermögen die Beschwerdeführer nicht darzutun, dass der angefochtene Entscheid betreffend Verjährung auf einem "Überlegungsfehler" beruhen würde, der Willkür begründen könnte. Die Vorinstanz verletzte somit kein Bundesrecht, indem sie die Klage insgesamt wegen Verjährung abwies (Erwägung 2 vorne).
5. Die Beschwerde ist demnach abzuweisen, soweit die erhobene Willkürrüge überhaupt den Begründungsanforderungen (Erwägung 3.2) genügt, und demnach darauf einzutreten ist. Bei diesem Verfahrensausgang werden die Beschwerdeführer unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 5'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 6'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 12. November 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Widmer