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.