Sachverhalt:
A.
A.a. Die C._ AG (Vermieterin, Beklagte, Beschwerdegegnerin) erwarb am 6. Dezember 2001 die aneinander grenzenden Liegenschaften Strasse U._ und Strasse V._ in Zürich.
Der Kaufpreis betrug Fr. 21'529'000.--. Im Jahre 2012 baute die Vermieterin die beiden Liegenschaften um, wofür sie der Generalunternehmerin Fr. 7'007'960.-- bezahlte; für Zusatzarbeiten leistete sie überdies noch Fr. 896'372.--. Nach dem Umbau wiesen die beiden Liegenschaften insgesamt 4'027 m2 Laden-, Restaurations-, Büro-, Lager-, Werkstatt- und Wohnräume auf. Unter anderem sind im Dachstock der beiden Liegenschaften insgesamt sechs 3.5-Zimmer-Maisonette-Wohnungen neu eingebaut worden.
A.b. Am 20. März 2013 schlossen A._ (Mieter 1, Kläger 1, Beschwerdeführer 1) und B._ (Mieter 2, Kläger 2, Beschwerdeführer 2) mit der Vermieterin einen Vertrag über die Miete einer der 3.5-Zimmer-Maisonette-Wohnungen im Dachstock der Liegenschaft Strasse U._ in Zürich. Der Mietzins wurde auf Fr. 3'900.-- zuzüglich Fr. 300.-- Nebenkosten à-conto pro Monat festgesetzt. Die Mieter verpflichteten sich überdies, eine Sicherheit von Fr. 12'600.-- zu leisten. Als Mietbeginn wurde der 1. April 2013 festgelegt. Die Mieter arbeiteten beide bei einer Bank in Genf und wurden nach Zürich versetzt. Sie verdienten im Jahr 2013 netto knapp Fr. 80'000.-- bzw. Fr. 100'000.-- und mieteten die Wohnung ab Arbeitsantritt des Mieters 1 gemeinsam, um sich die Kosten zu teilen; der Mieter 2 hatte zuvor in Zürich seit August 2012 ein möbliertes Studio gemietet.
B.
B.a. Mit Eingabe vom 23. April 2013 gelangten die Mieter an die Schlichtungsbehörde Zürich mit dem Antrag, es sei der Anfangsmietzins für missbräuchlich zu erklären und um Fr. 1'100.-- herabzusetzen.
Die Schlichtungsstelle stellte mangels Einigung am 26. August 2013 die Klagebewilligung aus.
B.b. Die Mieter gelangten noch am gleichen Tag an das Mietgericht und stellten mit den in der Folge modifizierten Rechtsbegehren schliesslich die Anträge, es sei der Anfangsmietzins für die 3.5-Zimmer-Maisonette-Wohnung als missbräuchlich zu erklären, soweit er monatlich netto Fr. 2'200.-- übersteigt; die hinterlegte Mietzinsgarantie sei auf Fr. 6'600.-- zu reduzieren.
Mit Urteil vom 16. Juni 2015 wies das Mietgericht Zürich die Klage ab.
Das Mietgericht erwog zunächst, dass die Voraussetzungen für eine Anfechtung des Anfangsmietzinses wegen der Verhältnisse auf dem örtlichen Markt für Wohnräume gemäss Art. 270 Abs. 1 lit. a OR (trotz in der Begründung vorgebrachter Vorbehalte) gegeben seien, weshalb letztlich offen bleiben könne, ob auch eine persönliche Notlage der Mieter vorgelegen habe. Das Gericht kam jedoch zum Schluss, den Mietern sei der ihnen obliegende Nachweis nicht gelungen, dass die Vermieterin einen übersetzten Ertrag aus der Mietwohnung erziele.
B.c. Das Obergericht des Kantons Zürich wies mit Urteil vom 9. November 2015 die Berufung der Mieter ab und bestätigte das erstinstanzliche Urteil.
Zur Begründung führte das Obergericht aus, es genüge für die Anfechtung des Anfangszinses nach Art. 270 Abs. 1 lit. a OR nicht, wenn der Mieter eine Notlage oder eine Wohnungsnot nachweise; er müsse vielmehr beweisen, dass er sich aus diesem Grund in einer Zwangslage befunden habe, und er müsse nachweisen, dass ihm eine vernünftige Alternative gefehlt habe, wozu er Suchbemühungen nachzuweisen habe. Dass er diesen Nachweis zu erbringen habe, entspreche der Praxis des zürcherischen Obergerichts, die nach dessen Ansicht vom Bundesgericht bestätigt worden sei, das dann aber im Widerspruch dazu entschieden habe, es verletze Bundesrecht, bei Wohnungsnot vom Mieter den Nachweis von Suchbemühungen zu verlangen. Das Obergericht schloss, die Kläger seien zum Nachweis der Missbräuchlichkeit des Anfangsmietzinses nicht zuzulassen, da sie eine Zwangslage nicht nachgewiesen hätten.
C.
Mit Beschwerde in Zivilsachen vom 15. Dezember 2015 beantragen die Mieter dem Bundesgericht, das Urteil des Obergerichts des Kantons Zürich vom 8. November 2015 sei aufzuheben und das Verfahren sei zum Entscheid über die Missbräuchlichkeit des Anfangsmietzinses an die Vorinstanz zurückzuweisen, eventualiter sei der Anfangsmietzins für missbräuchlich zu erklären, soweit er monatlich netto Fr. 2'200.-- übersteigt, und die Mietkaution sei entsprechend zu reduzieren.
Die Beschwerdeführer rügen die Verletzung von Art. 270 Abs. 1 lit. a OR. Zur Begründung des Eventualantrages kritisieren sie die Erwägungen des erstinstanzlichen Mietgerichts.
Die Beschwerdegegnerin beantragt in ihrer Vernehmlassung die Abweisung der Beschwerde. Die Vorinstanz hat auf Vernehmlassung verzichtet.
Erwägungen:
1.
1.1. Die Beschwerde richtet sich gegen den Endentscheid (Art. 90 BGG) eines oberen kantonalen Gerichts, das in einer Zivilsache (Art. 72 BGG) als Rechtsmittelinstanz entschieden (Art. 75 BGG) und die Anträge der Beschwerdeführer abgewiesen hat (Art. 76 BGG). Der Streitwert in der vorliegenden Mietangelegenheit (Art. 74 Abs. 1 lit. a BGG) ist erreicht und die Beschwerdefrist (Art. 100 BGG) ist eingehalten.
1.2. Die Beschwerde in Zivilsachen ist ein reformatorisches Rechtsmittel (Art. 107 Abs. 2 BGG). Der Beschwerdeführer darf sich deshalb nicht darauf beschränken, die Aufhebung des angefochtenen Entscheids zu beantragen, sondern muss einen Antrag in der Sache stellen (BGE 134 III 379 E. 1.3 S. 383). Eine Ausnahme vom Erfordernis, reformatorische und fallbezogen bezifferte Begehren zu stellen, besteht jedoch dann, wenn das Bundesgericht im Falle der Gutheissung in der Sache nicht selbst entscheiden könnte, insbesondere weil die erforderlichen Sachverhaltsfeststellungen der Vorinstanz fehlen (BGE 133 III 489 E. 3.1 S. 490; 135 III 31 E. 2.2 S. 33; vgl. auch BGE 136 III 269 E. 5.2 S. 272/273). Dies trifft hier zu.
Die Vorinstanz hat die Voraussetzungen für die Anfechtung des Anfangsmietzinses verneint und aus diesem Grund nicht beurteilt, ob der umstrittene Zins missbräuchlich sei. Die Beschwerdeführer setzen sich denn auch in der Begründung ihres Eventualantrags ausschliesslich mit den Erwägungen des Mietgerichts auseinander, was angesichts des Erfordernisses der kantonalen Letztinstanzlichkeit des angefochtenen Entscheides (Art. 75 BGG) nicht zulässig ist.
Der Hauptantrag auf Rückweisung der Sache ist zulässig, auf den eventualiter gestellten Antrag auf Feststellung der Missbräuchlichkeit des Mietzinses ist nicht einzutreten.
1.3. Nach Art. 105 Abs. 1 BGG legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Dazu gehören sowohl die Feststellungen über den Lebenssachverhalt als auch jene über den Prozesssachverhalt (BGE 140 III 16 E. 1.3.1 S. 18). Gerügt werden kann nach Art. 97 BGG eine offensichtlich unrichtige, d.h. willkürliche (Art. 9 BV; BGE 135 III 127 E. 1.5 S. 130 mit Hinweis) Sachverhaltsfeststellung oder eine Rechtsverletzung bei der Sachverhaltsermittlung.
Die Beschwerdeführer rügen nicht, die Vorinstanz habe den Sachverhalt willkürlich oder in Verletzung von Recht (Art. 95 BGG) festgestellt. Es ist auf der Grundlage der Tatsachenfeststellungen im angefochtenen Urteil zu entscheiden.
2.
Art. 270 Abs. 1 OR lässt die Anfechtung des Anfangsmietzinses durch den Mieter zu, wenn
"a. er sich wegen einer persönlichen oder familiären Notlage oder wegen der Verhältnisse auf dem örtlichen Markt für Wohnungen und Geschäftsräume zum Vertragsabschluss gezwungen sah; oder
b. der Vermieter den Anfangsmietzins gegenüber dem früheren Mietzins für dieselbe Sache erheblich erhöht hat."
In der französischen Fassung:
"a. s'il a été contraint de conclure le bail par nécessité personnelle ou familiale ou en raison de la situation sur le marché local du logement et des locaux commerciaux; ou
b. si le bailleur a sensiblement augmenté le loyer initial pour la même chose par rapport au précédent loyer."
In der italienischen Fassung:
"a. è stato costretto a concludere il contratto per necessità personale o familiare oppure a causa della situazione del mercato locale di abitazioni e di locali commerciali; o
b. il locatore ha aumentato in modo rilevante la pigione iniziale rispetto a quello precedente per la stessa cosa."
2.1. Die Anfechtung des Anfangsmietzinses war schon vor Inkrafttreten des am 15. Dezember 1989 geänderten 8. Titels des Obligationenrechts über die Miete (AS 1990, S. 802) in Art. 17 des Bundesbeschlusses über Missbräuche im Mietwesen (BMM) vorgesehen. Nach Art. 17 BMM war die Anfechtung des Mietzinses beim Abschluss eines Mietvertrages innert einer Frist von dreissig Tagen zunächst voraussetzungslos zulässig. Denn Art. 17 BMM in der ursprünglichen Fassung vom 30. Juni 1972 (AS 1972, S. 1502 ff./1507) sah vor: "Der Mieter einer Wohnung, die erstmals oder wieder vermietet wird, ist berechtigt, innert dreissig Tagen seit Abschluss des Mietvertrages den Mietzins als missbräuchlich bei der Schlichtungsstelle anzufechten". Mit der Änderung des BMM vom 9. Juni 1977 wurde die Anfechtung des Anfangsmietzinses dagegen an die Bedingung einer Notlage geknüpft. Art. 17 BMM erhielt folgenden Wortlaut: "Der Mieter einer Wohnung kann innert 30 Tagen nach Abschluss des Mietvertrages den Mietzins bei der Schlichtungsstelle als missbräuchlich anfechten, wenn er sich wegen einer Notlage zum Vertragsabschluss gezwungen sah" (AS 1977, S. 1269 ff./1270).
Diese Entwicklung wurde vom Bundesgericht im publizierten Urteil BGE 114 II 74 E. 3c S. 76 ff. dargestellt und es wurde aufgezeigt, dass der Bundesrat die ursprüngliche Norm beibehalten wollte, die Anfechtbarkeit jedoch von Vermieterseite heftig kritisiert worden war. Art. 17 BMM in der Fassung vom 9. Juni 1977 wurde vom Bundesgericht in diesem publizierten Urteil als Kompromiss verstanden und im Lichte der Entstehungsgeschichte so ausgelegt, dass der Mieter den Anfangsmietzins nicht nur anfechten könne in einer Situation der Wohnungsnot, sondern auch unabhängig von einer derartigen Situation, wenn er zum Abschluss der Miete aus anderen persönlichen Gründen gezwungen war (BGE 114 II 74 E. 3c S. 77). Ausdrücklich verworfen wurde in diesem Urteil die Auslegung von Art. 17 BMM durch die Vorinstanz, welche eine Notlage nur hatte bejahen wollen, wenn der Mieter nachweise, dass er dringend die Wohnung wechseln musste, sich finanziell keine teurere Wohnung leisten konnte und intensiv und lange gesucht hatte (BGE 114 II 74 E. 3d S. 78).
Im Jahr 1985 schlug der Bundesrat dem Parlament schliesslich vor, den Bundesbeschluss über Missbräuche im Mietwesen durch ein Bundesgesetz über Massnahmen gegen Missbräuche im Mietwesen (BGMM) zu ersetzen (BBl 1985, S. 1526). Art. 13 des entsprechenden Gesetzesentwurfs wollte dem Mieter das Recht einräumen, den Anfangsmietzins innert 30 Tagen nach Übergabe der Mietsache bei der Schlichtungsstelle als missbräuchlich anzufechten und die Herabsetzung zu verlangen. Ausweislich der Botschaft beabsichtigte der Bundesrat damit, das Recht zur Anfechtung eines missbräuchlichen Anfangsmietzinses wieder vom Nachweis einer Notlage zu befreien. Der Verzicht auf diese Voraussetzung war nach Auffassung des Bundesrats gerechtfertigt, weil der damals geltende Art. 17 BMM in der Praxis gerade deshalb toter Buchstabe geblieben sei, weil die Gerichte ihn restriktiv ausgelegt und höchst selten eine Notlage des Mieters angenommen hätten (Botschaft vom 27. März 1985 zur Revision des Miet- und Pachtrechts, BBl. 1985 1389, S. 1491). Die Anfechtung des Anfangsmietzinses gab in der Folge Anlass zu grundsätzlichen Diskussionsvoten in der parlamentarischen Auseinandersetzung (Amtl. Bull. SR 1988, S. 164-172; NR 1989, S. 520-529; SR 1989, S. 426-428; dazu PETER ZIHLMANN, Das Mietrecht, 2. Aufl., 1995, S. 185; SÉBASTIEN FETTER, La contestation du loyer initial, Diss. Bern 2005, Rz. 13 ff.). Nebst dem Vorschlag des Bundesrats, der das Recht zur Anfechtung missbräuchlicher Anfangsmietzinse von keiner Voraussetzung mehr abhängig machen wollte, lagen dem Nationalrat zwei weitere Vorschläge vor: Ein restriktiver Vorschlag von Herrn Nationalrat Gysin, der grundsätzlich dem damals geltenden Art. 17 BMM entsprach, wobei dieser einschränkend zu interpretieren gewesen wäre. Und schliesslich ein Kompromissvorschlag von Herrn Nationalrat Petitpierre, wonach in Übereinstimmung mit der Rechtsprechung von BGE 114 II 74 die beiden Bedingungen der persönlich-familiären Notlage und der Wohnungsnot nicht kumulativ, sondern alternativ zur Anfechtung des Anfangsmietzinses berechtigen sollen. Diese Lösung bestätige - so Petitpierre - zwar eine bestehende Rechtsprechungspraxis zu Art. 17 BMM, ermögliche aber im Gegensatz zum restriktiven Vorschlag Gysin eine offene Auslegung (Votum PETITPIERRE, Amtl. Bull. NR 1989, S. 520). Der Vorschlag Petitpierre fand schliesslich eine Mehrheit und wurde zum heutigen Art. 270 Abs. 1 lit. a OR.
2.2. Unter dem geltenden Recht hat das Bundesgericht erkannt, dass die Anfechtung nach Art. 270 Abs. 1 OR in drei alternativen Fällen möglich ist, nämlich wenn der Mieter aus persönlicher oder familiärer Notwendigkeit zum Abschluss des Vertrags gezwungen war (lit. a erste Alternative), wenn er wegen der Situation auf dem lokalen Wohnungsmarkt zum Vertragsabschluss gezwungen war (lit. a zweite Alternative) oder schliesslich wenn gemäss lit. b der Mietzins gegenüber demjenigen des Vormieters erheblich erhöht wurde (BGE 136 III 82 E. 2 S. 84). Ausdrücklich festgehalten wurde dabei, dass es für das Anfechtungsrecht genügt, wenn eine dieser drei Alternativen erfüllt ist. Die Kriterien, nach denen sich die Anfechtbarkeit des Anfangsmietzinses nach den drei Varianten je richtet (vgl. für lit. b BGE 139 III 13 E. 3.1.1 S. 15), sind dabei alternativ zu prüfen.
2.2.1. Persönliche oder familiäre Umstände, die nach der ersten Alternative von Art. 270 Abs. 1 lit. a OR die Anfechtbarkeit des Anfangsmietzinses rechtfertigen können, wurden in der bundesgerichtlichen Praxis bejaht, als einer Familie mit drei Kindern die bisherige Mietwohnung gekündigt wurde und der eine nicht verlängerbare Zeit von acht Monaten verblieb, um eine neue Wohnung zu finden (Urteil 4C.121/1999 vom 28. Juli 1999 E. 2d). Die persönliche oder familiäre Notlage wurde dagegen verneint, als eine alleinerziehende Mutter mit zwei Kindern einerseits nach Erhalt der Kündigung ihrer bisherigen Wohnung erst nach vier Monaten Suchbemühungen aufgenommen und sich damit begnügt hatte, sich für die Miete einer einzigen Wohnung zu bewerben, wobei sie andererseits eine sehr kurze Erstreckung akzeptiert hatte; unter diesen Umständen wurde angenommen, die Notlage sei selbstverschuldet (Urteil 4C.169/2002 vom 16. Oktober 2002 E. 2.3 - allerdings wurde die Anfechtung zugelassen, weil der Mietzins im Sinne von lit. b gegenüber dem Vormietzins erheblich erhöht worden war, E. 3).
2.2.2. Die Situation auf dem lokalen Markt für Wohnungen, die nach der zweiten Alternative von Art. 270 Abs. 1 lit. a OR die Anfechtung des Anfangsmietzinses rechtfertigt, wurde in der Rechtsprechung als hinreichend anerkannt, als ein Mieter im Kanton Genf eine 3-Zimmer-Wohnung gemietet hatte; das Bundesgericht stellte die Wohnungsnot in Genf als notorisch fest und liess die Anfechtung des Anfangsmietzinses nach Art. 270 Abs. 1 lit. a OR im Unterschied zur Vorinstanz zu, ausdrücklich ohne vom Mieter zusätzlich den Nachweis zu verlangen, dass ihn persönliche Umstände zum Abschluss des neuen Mietvertrages gezwungen hätten oder er trotz Suchbemühungen keine Wohnung zu einem nicht-missbräuchlichen Mietzins gefunden hätte (Urteil 4C.367/2001 vom 12. März 2002 E. 3b/dd). Die Anfechtung des Anfangsmietzinses wurde dagegen einer Mieterin in Freiburg verwehrt, die sich nur auf alte, nicht aussagekräftige Statistiken berufen konnte, und wo die Vorinstanz festgestellt hatte, dass der Bestand leerer Wohnungen in der Stadt Freiburg im massgebenden Zeitpunkt 2,29% betrug (BGE 136 III 82 E. 3 S. 85). Der Mangel an Wohnungen oder Geschäftsräumen kann nach einem weiteren Entscheid freilich vom Mieter nicht nur mit offiziellen Statistiken, sondern auch auf andere Weise (namentlich durch den Nachweis intensiver und fruchtloser Suchbemühungen) erbracht werden (Urteil 4A_250/2012 vom 28. August 2012 E. 2.2).
2.2.3. Die allgemeinen Erwägungen in den Entscheiden des Bundesgerichts zur Auslegung von Art. 270 Abs. 1 lit. a OR sind nicht einheitlich; zuweilen werden - unter Zusammenfassung der beiden Alternativen in Art. 270 Abs. 1 lit. a OR - nur zwei alternative Voraussetzungen erwähnt (vgl. etwa Urteil 4A_576/2008 vom 19. Februar 2009 E. 2.1). Regelmässig wird unter Hinweis auf den noch zu Art. 17 BMM ergangenen BGE 114 II 74 erwähnt, dass beide der alternativen Voraussetzungen in Art. 270 Abs. 1 lit. a OR die Ursache dafür bilden müssen, dass sich der Mieter "zum Vertragsschluss gezwungen sah" (vgl. BGE 136 III 82 E. 2; Urteile 4C.121/1999 vom 28. Juli 1999 E. 2c; 4C.367/2001 vom 12. März 2002 E. 3, publ. in: SJ 2002 I, S. 589; 4C.169/2002 vom 16. Oktober 2002 E. 2.1, publ. in: Pra 2003, Nr. 124 S. 661). Die Vorinstanz hat daraus abgeleitet, dass der Mieter eine persönliche Notwendigkeit zum Abschluss des Mietvertrages (namentlich die Notwendigkeit des Wohnungswechsels und hinreichende Suchbemühungen) auch im Falle bewiesener Knappheit auf dem örtlichen Markt für Wohnungen oder Geschäftsräume nachweisen müsse. Sie hat aus dieser Sicht als widersprüchlich erachtet, dass das Bundesgericht den Entscheid eines oberen kantonalen Gerichts wegen Bundesrechtswidrigkeit aufhob, als dieses neben der belegten Wohnungsnot weitere Anforderungen an die Zwangslage im Sinne von Art. 270 Abs. 1 lit. a OR stellte (Urteil 4C.367/2001 vom 12. März 2002 E. 3).
2.3. In der Literatur sind die Ansichten geteilt. Einerseits wird die Ansicht vertreten, die beiden in Art. 270 Abs. 1 lit. a OR aufgeführten Gründe für die Zulassung zur Anfechtung des Anfangsmietzinses setzten in jedem Fall auch den Nachweis voraus, dass der Mieter (aufgrund seiner persönlichen Situation) zum Abschluss des Mietvertrages gezwungen war, dass ihm somit keine zumutbare Alternative zur Verfügung gestanden habe (HIGI, in: Zürcher Kommentar, 4. Aufl. 1998, N. 36 ff./41 zu Art. 270 OR; TERCIER/FAVRE, Les contrats spéciaux, 4. Aufl., N. 2657 [freilich unter Verweis auf einen Entscheid der Genfer Cour de Justice vom 12. Februar 2001, deren Praxis im Urteil des Bundesgerichts 4C.367/2001 vom 12. März 2002 als bundesrechtswidrig erklärt worden ist]; BISANG et al., Das schweizerische Mietrecht, SVIT-Kommentar, 3. Aufl. 2009, N. 12 ff. zu Art. 270 OR; MÜLLER, Cahier du bail, 1995, S. 6; JORNOD, La contestation du loyer initial, ZSR 2006 I S. 49); ein anderer Teil der Lehre vertritt die Ansicht, dass der Nachweis der Wohnungsnot zur Anfechtung des Anfangsmietzinses gemäss der zweiten Alternative von Art. 270 Abs. 1 lit. a OR genüge (LACHAT, Le bail à loyer, 2008, S. 390; DERSELBE, Commentaire Romand, 2. Aufl., 2012, N. 5 zu Art. 270 OR; WEBER, in: Basler Kommentar, 6. Aufl., 2015, N. 4 zu Art. 270 OR; BOHNET/MONTINI, Droit du bail à loyer, Commentaire pratique, 2010, N. 28/36 zu Art. 270 OR; ZAHRADNIK, Fragen im Zusammenhang mit der Anfechtung der Anfangsmiete und der Formularpflicht, mp 2014, S. 267 ff., 277; FETTER, a.a.O., Rz. 381).
3.
Die Vorinstanz hat entgegen dem Mietgericht die Voraussetzung von Art. 270 Abs. 1 lit. a OR mit der Begründung verneint, die Kläger hätten die erforderliche Zwangslage nicht nachgewiesen. Denn nach der Auslegung der Vorinstanz genügt nicht, wenn der Mieter eine Wohnungsnot nachweist. Er muss zudem nachweisen, dass er sich (aufgrund seiner persönlichen Umstände) in einer Zwangslage befunden hat, und diese Zwangslage muss kausal auf die Notlage oder die Wohnungsnot zurückzuführen sein.
3.1. Das Gesetz muss in erster Linie aus sich selbst heraus, das heisst nach dem Wortlaut, Sinn und Zweck und den ihm zugrunde liegenden Wertungen auf der Basis einer teleologischen Verständnismethode ausgelegt werden. Die Gesetzesauslegung hat sich vom Gedanken leiten zu lassen, dass nicht schon der Wortlaut die Norm darstellt, sondern erst das an Sachverhalten verstandene und konkretisierte Gesetz. Gefordert ist die sachlich richtige Entscheidung im normativen Gefüge, ausgerichtet auf ein befriedigendes Ergebnis der ratio legis. Dabei befolgt das Bundesgericht einen pragmatischen Methodenpluralismus und lehnt es namentlich ab, die einzelnen Auslegungselemente einer hierarchischen Prioritätsordnung zu unterstellen (BGE 141 III 195 E. 2.4 S. 198 f.; 140 III 206 E. 3.5.4; 140 IV 1 E. 3.1; je mit Hinweisen).
3.1.1. Ausgangspunkt jeder Auslegung ist der Wortlaut. Gemäss dem Wortlaut von Art. 270 Abs. 1 lit. a OR ermöglichen zwei Alternativen die Anfechtung. In allen drei Sprachen werden als Grund für den Zwang zum Abschluss des Mietvertrages entwedereine persönliche bzw. familiäre Notlage oder die Verhältnisse auf dem örtlichen Markt für Wohnungen oder Geschäftsräume angeführt (oben E. 2.1). Es ist daher davon auszugehen, dass nach Art. 270 Abs. 1 OR drei Gründe für die Anfechtung des Anfangsmietzinses bestehen, nämlich nach der ersten Alternative in Art. 270 Abs. 1 lit. a OR eine persönliche oder familiäre Notlage, die den Mieter zum Abschluss des - angefochtenen - Vertrages gezwungen hat, nach der zweiten Alternative in Art. 270 Abs. 1 lit. a OR die Verhältnisse auf dem örtlichen Wohnungsmarkt, die den Mieter zum Abschluss dieses Vertrages gezwungen haben, und schliesslich der - hier nicht angerufene - dritte Grund der erheblichen Erhöhung des Mietzinses gegenüber dem Vormieter gemäss Art. 270 Abs. 1 lit. b OR. Der Wortlaut ist klar: Es gibt drei alternative Gründe, die zur Anfechtung des Anfangsmietzinses berechtigen. Dies wurde im amtlich publizierten Urteil BGE 136 III 82 denn auch so festgehalten.
3.1.2. Systematisch sind zwar die beiden ersten Gründe der Anfechtung in einer einzigen lit. a aufgeführt, während der dritte Grund der Erhöhung des Mietzinses gegenüber dem Vormieter in einer eigenen lit. b steht. Daraus könnte auf den ersten Blick geschlossen werden, dass die beiden ersten Gründe auch materiell miteinander verbunden sind. Dies trifft indes nur insoweit zu, als in den beiden Fällen der lit. a die Umstände des Vertragsschlusses - nicht dessen inhaltliche Änderung gegenüber dem Vormietvertrag wie in lit. b - zur Anfechtung berechtigen. Dass letztlich persönliche bzw. familiäre Gründe nur in Verbindung mit den Verhältnissen auf dem lokalen Markt für Wohnungen oder Geschäftsräume zur Anfechtung der Anfangsmiete berechtigen könnten, kann daraus angesichts des klaren Wortlauts indessen gerade nicht abgeleitet werden. Soweit in gewissen Präjudizien formuliert wird, es beständen in Art. 270 Abs. 1 OR (nur) zwei Alternativen (vgl. oben E. 2.3; Urteil 4A_576/2008 vom 19. Februar 2009 E. 2.1) - kann daran nicht festgehalten werden, zumal der Frage im erwähnten Entscheid ohnehin keine Bedeutung zukam, da aus prozessualen Gründen nicht mehr zu prüfen war, ob die Voraussetzungen nach Art. 270 Abs. 1 OR vorlagen.
3.1.3. Weder aus der systematischen Stellung der beiden Anfechtungsgründe nach Art. 270 Abs. 1 lit. a OR noch aus der Entstehungsgeschichte (dazu oben E. 2.1) kann zudem abgeleitet werden, dass die Zwangslage des Mieters beim Abschluss des Mietvertrages qualitativ dieselbe sein müsse, unbesehen darum, ob sie auf eine persönliche bzw. familiäre Notlage oder auf die Verhältnisse im örtlichen Markt von Wohnungen oder Geschäftsräumen zurückzuführen sei. Dies ergibt sich insbesondere nicht daraus, dass mit dem im Parlament erreichten Kompromiss von Art. 270 Abs. 1 lit. a OR im Wesentlichen auf die Praxis des Bundesgerichts zu Art. 17 BMM zurückgegriffen worden ist (oben E. 2.1; dazu auch FETTER, a.a.O., Rz. 327).
3.1.3.1. In der Praxis zu Art. 17 BMM sind die beiden Gründe für die Anfechtung namentlich im amtlich publizierten BGE 114 II 74 als Voraussetzungen erwähnt, unter denen eine "Notlage" anzunehmen ist, die nach Art. 17 BMM für die Anfechtbarkeit des Anfangsmietzinses erforderlich war. In diesem Fall ging es um einen Mieter, dem die Anfechtung des Anfangsmietzinses vom Obergericht des Kantons Genf mit der Begründung verweigert worden war, die Anfechtung nach dem damaligen Art. 17 BMM sei als Ausnahme vom Grundsatz pacta sunt servanda nur sehr restriktiv zuzulassen. Das Bundesgericht folgte in diesem Urteil namentlich der Auffassung der Vorinstanz nicht, wonach der Mieter in jedem Fall die Dringlichkeit des Wohnungswechsels, die finanzielle Situation des Mieters wie auch die Anzahl und Dauer seiner Suchbemühungen nachzuweisen habe, ohne dass die Knappheit des Wohnungsangebots genüge (BGE 114 II 74 E. 3a S. 75 f.). Das Bundesgericht kam in Würdigung der Materialien zum Schluss, der Gesetzgeber habe die Anfechtungsmöglichkeit beim Vertragsschluss gegenüber dem früheren Rechtszustand nicht noch weiter beschränken wollen und der Mieter sei zur Anfechtung des Anfangsmietzinses berechtigt, wenn er zum Abschluss eines neuen Mietvertrages gezwungen war, sei es infolge der Wohnungsnot oder wegen einer persönlichen schwierigen Situation ("... que ce soit en raison de la pénurie de logements ou de difficultés liées à sa situation personnelle"). Eine Notlage im Sinne von Art. 17 BMM setze nicht eine Vernichtung des Willens voraus ("... ne suppose pas une annihilation de la volonté"; BGE 114 II 74 E. 3c S. 77).
3.1.3.2. Im erwähnten Urteil hat das Bundesgericht im Ergebnis die Voraussetzung zur Anfechtung des Anfangsmietzinses bejaht und die Sache zur materiellen Beurteilung der Missbräuchlichkeit des Anfangsmietzinses an die Vorinstanz zurückgewiesen. Es hat zwar ausdrücklich festgehalten, dass die drei von der Vorinstanz erwähnten Kriterien (Dringlichkeit des Wohnungswechsels, finanzielle Verhältnisse des Mieters, Anzahl und Dauer der Suchbemühungen) für die Anwendung von Art. 17 BMM nicht entscheidend sind (BGE 114 II 74 E. 3d S. 78). Es hat jedoch in diesem Urteil angenommen, es genüge für die Notlage, dass der Mieter gute Gründe für den Wohnungswechsel habe und dass von ihm nicht verlangt werden könne, auf eine Gelegenheit zum Abschluss eines Mietvertrages zu verzichten - sei es wegen der Marktsituation oder wegen seiner persönlichen Verhältnisse, wobei sämtliche Umstände zu berücksichtigen seien zur Beurteilung, ob eine Notlage im Sinne von Art. 17 BMM vorliege.
3.1.3.3. Altrechtlich war nach Art. 17 BMM eine "Notlage" des Mieters erforderlich, damit der Anfangsmietzins angefochten werden konnte. Wenn das Bundesgericht in Auslegung dieser Norm namentlich aufgrund der Entstehungsgeschichte (BGE 114 II 74 E. 3c S. 77) schloss, dass der Gesetzgeber die Anfechtung des Anfangsmietzinses nicht nur bei Wohnungsnot, sondern auch aus anderen Gründen zulassen wollte, so war im konkreten Fall doch in Anwendung von Art. 17 BMM zu beurteilen, ob im Ergebnis eine "Notlage" im Sinne dieser Norm vorlag. Zur Beurteilung dieser Frage erkannte das Bundesgericht, dass sämtliche - persönlichen und objektiven - Umstände zu berücksichtigen seien, und entsprechend prüfte es auch im konkreten Fall, ob der Mieter hinreichende Gründe für einen Wohnungswechsel hatte, die zusammen mit der notorischen Wohnungsnot im Kanton Genf eine "Notlage" im Sinne von Art. 17 BMM begründeten. Wenn daher bei der Auslegung von Art. 270 Abs. 1 lit. a OR berücksichtigt wird, dass die geltende Norm auf einen Kompromiss des Gesetzgebers zurückgeht, der sich in dieser umstrittenen Frage von der Praxis des Bundesgerichts zur alten Bestimmung leiten liess, so kann methodisch nicht unbeachtet bleiben, dass die Norm geändert wurde - dies nicht nur mit dem Einbezug von Geschäftsräumen, sondern auch mit einer anderen Formulierung: Eine persönliche oder familiäre "Notlage", wegen deren sich der Mieter zum Vertragsabschluss gezwungen sah, wird als selbständige Alternative zu den Verhältnissen auf dem örtlichen Markt für Wohnungen oder Geschäftsräume aufgeführt, wegen denen sich der Mieter zum Abschluss des Vertrages (zum entsprechenden Preis) gezwungen sah. Die "Notlage", die stets eine Würdigung der gesamten Verhältnisse erfordert, ist nach geltendem Recht nur noch für die erste Alternative in Art. 270 Abs. 1 lit. a OR verlangt. Aus dem Umstand, dass sich der Gesetzgeber von der geltenden bundesgerichtlichen Praxis anregen liess, kann dagegen nicht abgeleitet werden, es sei der Grundsatz beibehalten worden, wonach im Ergebnis eine "Notlage" bzw. eine entsprechende "Zwangslage" des Mieters auch bei ausgewiesener Wohnungsnot erforderlich sei, wie sie altrechtlich von Art. 17 BMM verlangt wurde.
3.1.4. Es ist auch teleologisch nicht einzusehen, weshalb für die Anfechtung des Anfangsmietzinses wegen einer nicht funktionierenden Marktlage der Nachweis einer persönlichen Not- bzw. Zwangslage erforderlich sein sollte. Der Grundsatz pacta sunt servanda gilt uneingeschränkt und gehört gar zum ordre public, wenn gleichberechtigte und vergleichbar marktmächtige Kontrahenten einen Vertrag schliessen. Es ist nun jedoch eine Binsenwahrheit, dass Konsumenten im Allgemeinen und Mieter im Besonderen keine den Anbietern vergleichbare Stellung einnehmen, die ihnen die Verhandlung eines ausgewogenen Vertrages ermöglichen könnte. Um den Missbrauch eines Marktungleichgewichts zu verhindern, hat sich der Gesetzgeber deshalb gezwungen gesehen, die herkömmlichen Anfechtungsgründe wegen Willensmängeln (Art. 23 f. OR) und Übervorteilung (Art. 21 OR; vgl. dazu etwa BGE 123 III 292 E. 5 S. 301) in besonderen Konstellationen zu ergänzen (vgl. etwa Art. 40a ff. OR für Haustürgeschäfte und ähnliche Verträge). Im Mietrecht hat sich erwiesen, dass beim Neuabschluss von Verträgen die Gefahr missbräuchlicher Mietzinse namentlich dann besteht, wenn der Bestand an verfügbaren Wohnungen (und Geschäftsräumen) so gering ist, dass ein Interessent den Vertrag auch dann schliesst, wenn der Anbieter missbräuchliche Preise verlangt. In diesen Fällen besteht rein aufgrund der Marktlageein Zwang zum Abschluss des Mietvertrages - auch zu missbräuchlichen Bedingungen. Um dieser Gefahr zu begegnen, ermöglicht die zweite Alternative von Art. 270 Abs. 1 lit. a OR die Überprüfung des Anfangsmietzinses auf Missbrauch während der 30-tägigen Anfechtungsfrist. In der Literatur wird zutreffend darauf hingewiesen, es sei vom Gesetz vorausgesetzt, dass sich die Marktlage bei Knappheit an Wohnungen oder Geschäftsräumen beim Vertragsschluss konkret bemerkbar macht (WEBER, in: Basler Kommentar, N. 4 zu Art. 270 OR). Die Knappheit des Angebots verschafft den Anbietern auf dem Wohnungsmarkt eine Stellung, die derjenigen marktmächtiger Unternehmen nahekommt. Die Anfechtung missbräuchlicher Mietzinse gestützt auf die zweite Alternative von Art. 270 Abs. 1 lit. a OR dient insoweit der gleichen Zielsetzung wie die Preisüberwachung oder die Kartellgesetzgebung (vgl. etwa PIERRE TERCIER, Droit des cartels et surveillance des prix, in: Roger Zäch [Hrsg.], Kartellrecht auf neuer Grundlage, 1989, S. 336 ff.; KÜNZLER/ZÄCH, in: Oesch et al. [Hrsg.], Wettbewerbsrecht II, 2011, N. 6 zu Art. 1 PüG; SCHÜRMANN/SCHLUEP, KG + PüG, 1988, S. 800). Dass die zivilrechtlichen Rechtsbehelfe zur Korrektur eines Marktungleichgewichts nur voraussetzen, dass der Vertrag vom marktmächtigen Partner diktiert wird, ohne auch noch einen auf einer persönlichen Notlage beruhenden Vertragsabschlusszwang zu erfordern, ist in der massgebenden Literatur anerkannt (vgl. TERCIER, a.a.O., S. 336 ff.). Mit der zweiten Alternative von Art. 270 Abs. 1 lit. a OR soll einzig das Marktungleichgewicht beim Vertragsschluss eine Prüfung des Mietzinses auf Missbräuchlichkeit ermöglichen.
3.1.5. Die in der Literatur (vgl. namentlich HIGI, in: Zürcher Kommentar, N. 36 ff. zu Art. 270 OR) vertretene Ansicht, dass der Mieter auch bei nachgewiesener Knappheit des Mietangebots an Wohnungen oder an Geschäftsräumen auf dem örtlichen Markt zur Anfechtung des Anfangsmietzinses nur zuzulassen sei, wenn er nachweise, dass er aufgrund seiner persönlichen Verhältnisse zum Auszug aus seiner bisherigen Wohnung gezwungen war und keine zumutbare Alternative zum Abschluss eines anderen Vertrages hatte, beruht auf der Annahme, dass sich die gesetzliche Regelung nicht geändert habe. Während jedoch Art. 17 BMM in jedem Fall eine Notlage als Voraussetzung für die Anfechtung verlangte, war in BGE 114 II 74 - trotz der alternativ formulierten Voraussetzungen der persönlich-familiären Situation und der Marktsituation - die Würdigung sämtlicher Umstände des konkreten Falles erforderlich, um die gesetzliche Voraussetzung der Notlage zu beurteilen. Demgegenüber verlangt Art. 270 Abs. 1 lit. a OR für die Anfechtung des Anfangsmietzinses wegen der Verhältnisse auf dem örtlichen Markt für Wohnungen und Geschäftsräume - im Unterschied zur ersten Alternative der Notlage - nurmehr, dass sich der Mieter aus diesem Grund (und gerade nicht aus persönlichen Gründen) zu den vom marktmächtigen Vermieter diktierten Preisbedingungen zum Vertragsabschluss gezwungen sah.
3.1.6. Die Ansicht der Vorinstanz, wonach die Beschwerdeführer nicht nur die Knappheit des Mietangebots von Wohnungen in Zürich im massgebenden Zeitpunkt nachzuweisen hätten, sondern auch noch beweisen müssten, dass sie aufgrund ihrer persönlichen Situation keine zumutbare Alternative gehabt hätten, verkennt die Selbständigkeit der zweiten Voraussetzung zur Anfechtung des Anfangsmietzinses in Art. 270 Abs. 1 lit. a OR. Der Vorinstanz ist zwar zuzugestehen, dass die bundesgerichtliche Praxis nicht eindeutig ist, soweit zuweilen unkritisch allgemeine Formulierungen aus einem Urteil zum alten Recht bzw. aus der Literatur übernommen werden (vgl. etwa BGE 136 III 82 E. 2 S. 84 f. und Urteil 4A_169/2002 vom 16. Oktober 2002 E. 2.1). Wenn aus diesen allgemeinen Formulierungen geschlossen werden könnte, dass die altrechtliche "Notlage" neurechtlich mit der resultierenden "Zwangslage" weitergeführt worden sei, so ergibt sich aus den konkret entschiedenen Fällen das Gegenteil: Die bundesgerichtliche Praxis hat in der Beurteilung der konkreten Fälle konsequent die drei Alternativen in Art. 270 Abs. 1 OR auseinandergehalten und bei der Beurteilung der zweiten Alternative von Art. 270 Abs. 1 lit. a OR nicht verlangt, dass persönliche Umstände berücksichtigt werden. Das Bundesgericht hat (im Urteil 4C.367/2001 vom 12. März 2002) im Gegenteil - wie die Vorinstanz richtig erkennt - ein kantonales Urteil aufgehoben, das die beiden Alternativen nach Art. 270 Abs. 1 lit. a OR wie im vorliegenden Fall nicht klar auseinandergehalten hat. Der vorliegende Fall zeigt im Übrigen, dass die Ansicht der Vorinstanz für die Überprüfung des Anfangsmietzinses im Ergebnis wiederum eine eigentliche persönliche Notlage verlangt, wenn sie als sachlichen Grund für den Neuabschluss eines Mietvertrages den Wechsel des Arbeitsortes von Genf nach Zürich nicht genügen lassen will. Ein derart einschränkendes Verständnis der Voraussetzungen zur Anfechtung angeblich missbräuchlicher Anfangsmietzinsen ist schon altrechtlich verworfen worden (BGE 114 II 74 E. 3d S. 78) und verkennt nach geltendem Recht die Selbständigkeit der zweiten Voraussetzung in Art. 270 Abs. 1 lit. a OR, die eben eine wettbewerbsrechtliche Dimension aufweist und von der persönlichen Situation des Mieters abstrahiert (oben E. 3.1.4).
3.2. Der Mangel an Wohnungen oder Geschäftsräumen im Sinne von Art. 270 Abs. 1 lit. a zweite Alternative OR kann grundsätzlich mit offiziellen Statistiken belegt werden. Vorausgesetzt ist, dass diese aktuell sind und auf verlässlichen und hinreichend differenzierten Erhebungen beruhen (BGE 136 III 82 E. 2 S. 86). Soweit verlässliche statistische Daten über den Prozentsatz der im massgebenden Zeitpunkt verfügbaren Bestand von Wohnungen nicht vorhanden sind, ist es dem Mieter auch abgesehen davon möglich, den ihm obliegenden Nachweis der Wohnungsnot auf andere Weise zu erbringen, namentlich durch den Nachweis intensiver und fruchtloser Suchbemühungen (Urteil 4A_250/2012 vom 28. August 2012 E. 2.2).
Im vorliegenden Fall hat die Vorinstanz im Gegensatz zur ersten Instanz offengelassen, ob die Wohnungsnot belegt sei. Sie hat zwar verneint, dass die Mieter Suchbemühungen nachgewiesen hätten, hat sich aber zu den vom Mietgericht herangezogenen Statistiken nicht geäussert. Sie hat freilich festgestellt, dass nach den Feststellungen des Mietgerichts aufgrund der eingereichten Statistik in der Stadt Zürich am 1. Juli 2013 0.11% der Wohnungen leer gewesen seien (im Vorjahr 0.1%) und im ganzen Kanton Zürich die Leerwohnungsziffer 0.61% betrage. Die Beschwerdegegnerin behauptet, sie habe - vor erster Instanz (nicht vor der Vorinstanz) - geltend gemacht, die Leerwohnungsziffer belege die Wohnungsnot nicht hinreichend; sie zieht einen Vergleich zwischen der Anzahl Personen, die im Jahre 2011 umgezogen sind im Verhältnis zur Gesamtzahl der Einwohner der Stadt und der Anzahl Wohnungen und will daraus ableiten, dass jedenfalls im Jahr 2011 die Chance, in der Stadt Zürich eine neue Wohnung zu finden, bei 21% gelegen habe. Die Rechnung ist freilich nicht nachvollziehbar: Denn es ist nicht bekannt, wie viele Personen vergeblich eine Wohnung gesucht haben. Wenn das Angebot an Wohnungen in einem bestimmten Zeitpunkt objektiv begrenzt ist, so kann die Intensität der Nachfrage im Vergleich zum Angebot nicht aus der Anzahl der Wohnungswechsel, sondern einigermassen verlässlich nur daraus erschlossen werden, wie viele Wohnungen leer geblieben sind. Die Anzahl bzw. der Prozentsatz verfügbarer Wohnungen in einem bestimmten Zeitpunkt ist insofern durchaus ein verlässlicher Massstab zur Beurteilung, ob das Angebot an Mietwohnungen oder -geschäftsräumen knapp ist. Da die Beschwerdegegnerin im Übrigen keine substanziierten Einwendungen gegen die amtlichen statistischen Grundlagen anführt und namentlich nicht behauptet, vor Vorinstanz Einwände erhoben zu haben, kann die Wohnungsknappheit im massgebenden Zeitpunkt als ausgewiesen gelten.
4.
Die Vorinstanz hat die Voraussetzung für die Anfechtung des Anfangsmietzinses nach Art. 270 Abs. 1 lit. a zweite Alternative OR zu Unrecht verneint. Der angefochtene Entscheid ist in Gutheissung der Beschwerde aufzuheben und die Sache ist zur Beurteilung der Höhe des Mietzinses auf dessen Missbräuchlichkeit an die Vorinstanz zurückzuweisen.
Bei diesem Ausgang des Verfahrens sind die Gerichtskosten der Beschwerdegegnerin aufzuerlegen (Art. 66 Abs. 1 BGG). Sie hat den Beschwerdeführern deren Parteikosten für das Verfahren vor Bundesgericht zu ersetzen (Art. 68 Abs. 2 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 9. November 2015 wird aufgehoben und die Sache wird zur Neubeurteilung an die Vorinstanz zurückgewiesen.
2.
Die Gerichtsgebühr von Fr. 5'000.-- wird der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt Fr. 6'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 18. Mai 2016
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Hurni