Sachverhalt:
A. Die Schwestern C._ und D._ als Vermieter schlossen am 8. Juli 2003 mit A. und B. X._ (Beschwerdeführer) als Mieter einen Mietvertrag über Geschäftsräumlichkeiten zur Nutzung für Gastronomiebetriebe in der Liegenschaft Z._strasse in Zürich ab. Am 14./30. Oktober 2003 mieteten die Beschwerdeführer von C._ auch eine 3-Zimmerwohnung im dritten Obergeschoss der gleichen Liegenschaft. Die Beschwerdeführer haben diese Mietobjekte seit einiger Zeit untervermietet.
Einem Schreiben des beklagtischen Rechtsvertreters vom 18. September 2008 lagen die Kündigungen des Restaurantmietvertrags per 31. Oktober 2008 und des Wohnungsmietvertrags per 31. März 2009 bei.
Mit Schreiben vom 23. September 2008 mahnte die Verwaltung Q._ AG gegenüber den Beschwerdeführern die ausstehenden Mietzinse für die Monate August und September 2008 über den Betrag von Fr. 20'103.50.
Am 10. Oktober 2008 fochten die Beschwerdeführer die beiden Kündigungen vom 18. September 2008 bei der Schlichtungsbehörde Zürich als ungültig an.
Mit Schreiben vom 14. Oktober 2008 setzte die Verwaltung den Beschwerdeführern gestützt auf <ref-law> eine letzte Zahlungsfrist für die ausstehenden Mietzinse für die Monate August bis Oktober 2008 im Gesamtbetrag von Fr. 30'461.50. Nach unbenütztem Ablauf dieser Frist werde das Mietverhältnis gekündigt und unverzüglich die Betreibung eingeleitet.
Mit amtlichen Formularen kündigte die Verwaltung am 18. November 2008 den Beschwerdeführern die beiden Mietverträge je auf den 31. Dezember 2008 wegen Zahlungsverzugs gemäss <ref-law>.
Am 15. Dezember 2008 fochten die Beschwerdeführer die Kündigungen vom 18. November 2008 bei der Schlichtungsbehörde an. An der Schlichtungsverhandlung vom 27. Januar 2009 wurde sowohl über die Kündigungen vom 18. September 2008 als auch über diejenigen vom 18. November 2008 verhandelt. Nach der Verhandlung zog der beklagtische Rechtsvertreter die Kündigungen vom 18. September 2008 zurück, so dass die Schlichtungsbehörde die entsprechenden Verfahren am 27. Januar 2009 zufolge Gegenstandslosigkeit abschrieb. Mit Beschluss vom gleichen Datum wies die Schlichtungbehörde die Klage betreffend Anfechtung der Kündigungen vom 18. November 2008 ab und stellte deren Gültigkeit per 31. Dezember 2008 fest.
B. Mit Klage vom 27. Februar 2009 verlangten die Beschwerdeführer beim Mietgericht Zürich die Feststellung, dass die Kündigungen vom 18. November 2008 unwirksam seien. Mit Urteil vom 4. März 2010 erklärte das Mietgericht in Abweisung der Klage die Kündigung vom 18. November 2008 auf den 31. Dezember 2008 als wirksam und gültig. Gleichzeitig merkte es den Rückzug des klägerischen Rechtsbegehrens Ziffer 3 (ev. Erstreckung des Mietverhältnisses bis 31. März 2013) vor.
Gegen das Urteil des Mietgerichts erklärten die Beschwerdeführer Berufung an das Obergericht des Kantons Zürich. Mit Beschluss vom 17. Juni 2010 wurde vorgemerkt, dass an Stelle der verstorbenen C._ die Y._ AG (Beschwerdegegnerin), welche die Aufgabe der Willensvollstreckerin übernommen hatte, neu als Beklagte - im Sinne einer Prozessstandschaft - in den Prozess eingetreten ist. Am 24. August 2010 beschloss das Obergericht, die Klage abzuweisen, unter gleichzeitiger Feststellung der Rechtsgültigkeit der Kündigungen vom 18. November 2008 betreffend der Mietverträge für das Restaurant etc. im EG und für die 3-Zimmerwohnung im 3. OG an der Z._strasse in Zürich.
C. Die Beschwerdeführer beantragen dem Bundesgericht mit Beschwerde in Zivilsachen, diesen Urteil (recte den Beschluss) des Obergerichts vollumfänglich aufzuheben. Es sei festzustellen, dass die von der Q._ AG am 18. November 2008 per 31. Dezember 2008 ausgesprochenen Kündigungen für Restaurant EG etc./3-ZW, 3. OG an der Z._strasse in Zürich unwirksam seien. Eventualiter sei die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Obergericht verzichtete auf eine Vernehmlassung.
Am 3. Januar 2011 reichten die Beschwerdeführer eine Replik zur Beschwerdeantwort ein.
Mit Präsidialverfügung vom 23. November 2010 wurde das Gesuch der Beschwerdeführer um Erteilung der aufschiebenden Wirkung abgewiesen.
Am 3. Januar 2011 wies die Präsidentin ein von den Beschwerdeführern persönlich eingereichtes Sistierungsgesuch ab.

Erwägungen:
1. Der angefochtene Beschluss des Obergerichts ist ein verfahrensabschliessender Endentscheid (<ref-law>). Damit ein kantonaler Entscheid mit Beschwerde in Zivilsachen angefochten werden kann, muss der Instanzenzug im Kanton erschöpft sein (<ref-law>). Gegen den angefochtenen Beschluss wäre die Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich offen gestanden. Die Beschwerdeführer können den Beschluss des Obergerichts somit nur insoweit anfechten, als im Rahmen der Beschwerde in Zivilsachen zulässige Rügen dem Kassationsgericht nicht unterbreitet werden konnten (<ref-ruling> E. 1.3 S. 527; <ref-ruling> E. 3.2, 3.4 und 3.5 S. 586 ff.). Der Streitwert übersteigt die Grenze nach <ref-law>. Unter Vorbehalt zulässiger Rügen und einer rechtsgenüglichen Begründung (<ref-law>) ist auf die Beschwerde einzutreten.
2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (BGE 135 III 397 E. 1.5; <ref-ruling> E. 1.2.2).
Die Beschwerdeführer haben gegen den angefochtenen Beschluss des Obergerichts keine Nichtigkeitsbeschwerde an das Kassationsgericht erhoben. Damit hätten sie nach <ref-law>/ZH namentlich geltend machen können, der angefochtene Beschluss beruhe zum Nachteil des Nichtigkeitsklägers auf einer aktenwidrigen oder willkürlichen tatsächlichen Annahme (Ziff. 2). Da sie dies unterlassen haben, sind sie mit entsprechenden Sachverhaltsrügen gegen den angefochtenen Beschluss des Obergerichts mangels Letztinstanzlichkeit ausgeschlossen. Zulässig wäre zu rügen, das Obergericht habe bei der Sachverhaltsermittlung <ref-law> verletzt. Solche Rügen erheben die Beschwerdeführer nicht. Demnach ist durchwegs vom Sachverhalt auszugehen, wie ihn das Obergericht festgestellt hat. Soweit die Beschwerdeführer ihrer Beschwerdebegründung einen davon abweichenden Sachverhalt zugrunde legen, kann darauf nicht eingetreten werden.
3. Ist der Mieter nach der Übernahme der Sache mit der Zahlung fälliger Mietzinse oder Nebenkosten im Rückstand, so kann ihm der Vermieter nach <ref-law> schriftlich eine Zahlungsfrist setzen und ihm androhen, dass bei unbenütztem Ablauf der Frist das Mietverhältnis gekündigt werde. Diese Frist beträgt bei Wohn- und Geschäftsräumen mindestens 30 Tage. Bezahlt der Mieter innert der gesetzten Frist nicht, so kann der Vermieter fristlos, bei Wohn- und Geschäftsräumen mit einer Frist von mindestens 30 Tagen auf Ende eines Monats kündigen (<ref-law>).
Der Mieter kann seine Schuld auch durch Verrechnung tilgen, wenn er die entsprechende Erklärung innerhalb der Zahlungsfrist abgibt und seine Gegenforderung wegen Vorliegens eines Vollstreckungstitels unbestreitbar, unbestritten oder bewiesen ist (<ref-ruling> E. 6b/bb; Urteil 4A_642/2009 vom 2. Februar 2010 E. 4.1 mit Hinweisen).
3.1 Vorliegend stellte die Vorinstanz fest, dass die Beschwerdeführer die gemahnten Mietzinse für die Monate August, September und Oktober 2008 im Gesamtbetrag von Fr. 30'462.50 nicht bezahlten. Innerhalb der in der Zahlungsaufforderung vom 14. Oktober 2008 angesetzten 30-tägigen Nachfrist, die am 14. November 2008 endete, hätten sie keine Verrechnung erklärt. Sowohl die von ihrem Rechtsvertreter anlässlich der Schlichtungsverhandlung vom 27. Januar 2009 erklärte Verrechnung als auch diejenige, die gemäss dessen E-Mail vom 17. November 2008 erfolgt sein soll, seien verspätet und könnten nicht berücksichtigt werden. Angesichts der Verspätung liess die Vorinstanz letztlich offen, ob das E-Mail vom 17. November 2008 überhaupt eine solche Verrechnungserklärung enthalte. Betreffend das E-Mail des Beschwerdeführers 1 vom 8. September 2008 hielt sie fest, dass dieses keine unzweideutige Verrechnungserklärung enthalte. Abgesehen davon habe sich dieses E-Mail nur auf "zwei offene Mieten" - offensichtlich gemeint die Beträge für August und September 2008 - bezogen, womit für das ebenfalls abgemahnte Mietzinsbetreffnis für Oktober 2008 immer noch ein Zahlungsverzug bestanden hätte, der zur Kündigung nach <ref-law> berechtigt hätte. Die Verwaltung habe nicht davon ausgehen müssen, dass der Beschwerdeführer 1 damit auch für künftige Mietzinsforderungen Verrechnung erkläre. Es brauche daher nicht entschieden zu werden, ob eine solche Verrechnungserklärung überhaupt bereits vor Entstehen der Verrechnungsmöglichkeit abgegeben werden könnte. Die Vorinstanz hielt schliesslich auch eine mündliche Verrechnungserklärung für nicht nachgewiesen. Da die Beschwerdeführer die ausstehenden Mietzinse innert der Nachfrist weder bezahlt noch durch Verrechnung getilgt hatten, erachtete die Vorinstanz die Voraussetzungen für eine ausserordentliche Kündigung wegen Zahlungsverzugs als erfüllt.
3.2 Die Beschwerdeführer bestreiten, dass die Voraussetzungen für eine ausserordentliche Kündigung nach <ref-law> gegeben sind. Vor Bundesgericht berufen sie sich nur noch darauf, dass im E-Mail des Beschwerdeführers 1 vom 8. September 2008 eine Verrechnungserklärung zu erblicken sei, und zwar auch für die Zukunft. Es sei darum gegangen, keine Mietzinse zu bezahlen bis zum Betrag, den die Beschwerdeführer für den Austausch der Motoren der Kältemaschinen im Restaurant bezahlt hätten. Die Vorinstanz habe in Verletzung von Art. 120 und 124 OR festgestellt, dass keine gültige Verrechnung erfolgt sei. In der Folge habe sie durch ihren Entscheid <ref-law> verletzt.
3.3 Die Rüge ist unbegründet:
Wenn zwei Personen einander Geldsummen oder andere Leistungen schulden, die ihrem Gegenstand nach gleichartig sind, kann jede ihre Schuld, insofern beide Forderungen fällig sind, mit ihrer Forderung verrechnen (<ref-law>). Eine Verrechnung tritt gemäss <ref-law> nur insofern ein, als der Schuldner dem Gläubiger zu erkennen gibt, dass er von seinem Recht der Verrechnung Gebrauch machen will. Die Verrechnungserklärung ist eine einseitige und empfangsbedürftige Willenserklärung des Verrechnenden. Sie kann ausdrücklich oder durch konkludentes Handeln erfolgen und muss den Willen des Verrechnenden in unzweideutiger Weise erkennen lassen. Aus der Erklärung oder aus den Umständen muss auch hervorgehen, welches die zu tilgende Hauptforderung und welches die Verrechnungsforderung ist. Besteht diesbezüglich Unklarheit, ist die Verrechnungserklärung unvollständig und daher wirkungslos (Urteil 4A_82/2009 vom 7. April 2009 E. 2; 4C.25/2005 vom 15. August 2005 E. 4.1, nicht publ. in: <ref-ruling>).
Die genannten Anforderungen an eine wirksame Verrechnungserklärung erfüllt das E-Mail des Beschwerdeführers 1 vom 8. September 2008 nicht. Wie die Vorinstanz mit Hinweis auf die erstinstanzliche Begründung zutreffend ausführt, enthält dieses keine unzweideutige Verrechnungserklärung. In diesem E-Mail wird eine Verrechnung lediglich in Erwägung gezogen, aber keine solche erklärt, wobei weder die Hauptforderung noch die Verrechnungsforderung klar bestimmt wird. Damit hat der Beschwerdeführer 1 keine eindeutige Verrechnungserklärung abgegeben. Aber selbst davon abgesehen, ist der Vorinstanz auch in der weiteren Argumentation zu folgen, dass ohnehin nicht alle drei ausstehenden Mietzinsbetreffnisse für die Monate August bis und mit Oktober 2008 erfasst wären. In dem besagten E-Mail ist ausdrücklich nur von "zwei offenen Mieten" die Rede. Es sind keine Anhaltspunkte dargetan, nach denen die Beschwerdegegnerin hätte annehmen müssen, dass auch für künftige Mietzinse Verrechnung erklärt werden sollte.
3.4 Die Vorinstanz verletzte mithin weder Art. 120 und 124 OR noch <ref-law>, indem sie erkannte, dass die gemahnten Mietzinse für die Monate August bis Oktober 2008 innert Frist nicht durch Verrechnung getilgt worden waren und demzufolge die Beschwerdegegnerin berechtigt war, gestützt auf <ref-law> wegen Zahlungsverzugs zu kündigen.
4. Erstmals vor Bundesgericht machen die Beschwerdeführer geltend, die Kündigungen verstiessen gegen Treu und Glauben im Sinne von <ref-law> und seien rechtsmissbräuchlich (<ref-law>) erfolgt. Sie werfen der Vorinstanz zunächst vor, diesen "Aspekt" trotz der Pflicht zur Rechtsanwendung von Amtes wegen nicht berücksichtigt zu haben. Dies geht fehl. So müssen sie sich selber zuschreiben, dass sie sich im kantonalen Verfahren nicht auf Treuwidrigkeit bzw. Rechtsmissbräuchlichkeit der Kündigung berufen und diesbezüglich kein Tatsachenfundament vorgetragen haben. Ohne dass für eine missbräuchliche Kündigung sprechende Umstände offen zu Tage traten, war die Vorinstanz nicht gehalten, von sich aus nach Tatsachen zu forschen, aus denen auf einen Verstoss gegen Treu und Glauben hätte geschlossen werden können (vgl. <ref-ruling> E. 2.1; <ref-ruling> E. 1c S. 206).
Die Beschwerdeführer sind jedoch befugt, sich erst vor Bundesgericht auf die Verletzung von Treu und Glauben zu berufen, da es sich hierbei um einen rechtlichen Einwand handelt. Allerdings ist das Bundesgericht bei der Beurteilung desselben an den Sachverhalt gebunden, wie er von der Vorinstanz festgestellt wurde (<ref-ruling> E. 4.1 S. 366). Mit Ergänzungen und neuen tatsächlichen Vorbringen sind die Beschwerdeführer ausgeschlossen (vgl. Erwägung 2).
4.1 Nach <ref-law> ist die Kündigung anfechtbar, wenn sie gegen den Grundsatz von Treu und Glauben verstösst. Unter Umständen kann auch eine wegen Zahlungsverzugs ausgesprochene ausserordentliche Kündigung missbräuchlich im Sinne von <ref-law> sein, was aber nur ausnahmsweise in Betracht kommt (Urteile 4A_325/2010 vom 1. Oktober 2010 E. 5.1; 4C.59/2007 vom 25. April 2007 E. 3.4 und 4C.35/2004 vom 27. April 2004 E. 3.1, SJ 2004 I 424 ff.). So wurde etwa eine Kündigung als missbräuchlich qualifiziert, die der Vermieter angedroht hatte, bevor er über die rückständigen Beträge Gewissheit erlangt hatte, weshalb er die Bezahlung eines wesentlich übersetzten Betrages einforderte (<ref-ruling>). Ausserdem wurde die Kündigung in einem Fall als treuwidrig aufgehoben, als sich die Parteien in Verhandlungen über die Höhe einer grundsätzlich unbestrittenen Mietzinsreduktion befanden und die Situation im Zeitpunkt der Androhung und Erklärung der Kündigung höchst unklar war (Urteil 4C.65/2003 vom 23. September 2003 E. 4.2).
4.2 Die Beschwerdeführer berufen sich auf das zuletzt genannte Bundesgerichtsurteil und machen geltend, die Beschwerdegegnerin habe ihre Verrechnungserklärung vom 8. September 2008 einfach ignoriert und nichts zur Klärung der Lage unternommen. Auch auf die erneute Verrechnungserklärung vom 17. November 2008 sei keine Rückmeldung gekommen. Stattdessen habe die Beschwerdegegnerin postwendend die Kündigung der Mietverträge ausgesprochen. Ein solches Verhalten verstosse gegen Treu und Glauben.
Der vorliegende Fall ist nicht mit dem Urteil 4C.65/2003 vergleichbar. Im genannten Fall standen die Parteien in anhaltender Verhandlung über eine dem Grundsatz nach unbestrittene Mietzinsreduktion. Der Vermieter liess die Mieterin über die Höhe derselben im Ungewissen und kündigte wegen Zahlungsverzugs, als die Mieterin nach der Fristansetzung zur Bezahlung von zwei zurückbehaltenen Monatsmieten erklärt hatte, sie werde, falls es zu keiner Einigung über die Mietzinsreduktion komme, eine Mietzinshinterlegung vornehmen. Vorliegend ist nicht festgestellt, dass die angebliche Verrechnungsforderung der Beschwerdeführer dem Grundsatz nach unbestritten war oder dass die Parteien darüber in Verhandlung standen. Es ist daher nicht ersichtlich, dass und inwiefern die Beschwerdegegnerin eine Ungewissheit der Beschwerdeführer zu vertreten hatte, die zu klären sie gehalten gewesen wäre. Indem sie mit Schreiben vom 23. September 2008 die ausstehenden Mietzinse für die Monate August und September 2008 abmahnte, brachte sie im Übrigen unmissverständlich zum Ausdruck, dass sie die im E-Mail des Beschwerdeführers 1 vom 8. September 2008 von diesem als Frage aufgeworfene Verrechnung ablehnte. Eine von der Beschwerdegegnerin zu vertretende unklare Situation, die sie allenfalls nach Treu und Glauben zur Zurückhaltung mit der Erklärung der ausserordentlichen Kündigung hätte veranlassen müssen, ist im vorliegenden Fall nicht dargetan.
4.3 Die Beschwerdeführer halten die Kündigungen sodann für rechtsmissbräuchlich, weil mit der Verrechnungserklärung vom 17. November 2008 nur kurze Zeit (drei Tage) nach Ablauf der Zahlungsfrist die Ausstände getilgt worden seien. Dass die Beschwerdegegnerin diese Verrechnungserklärung ignoriert und daraufhin am 18. November 2008 die Kündigungen ausgesprochen habe, sei rechtsmissbräuchlich.
Es trifft zu, wie die Beschwerdeführer angeben, dass das Bundesgericht in einigen Entscheiden ausgeführt hat, dass eine treuwidrige Kündigung beispielsweise in Betracht fällt, wenn die Ausstände nur sehr kurze Zeit nach Ablauf der Zahlungsfrist beglichen worden sind und der Mieter zuvor immer pünktlich bezahlt hat (vgl. etwa die Urteile 4A_325/2010 vom 1. Oktober 2010 E. 5.1; 4C.65/2003 vom 23. September 2003 E. 4.2.1; 4C.173/2005 vom 24. Oktober 2005 E. 2.2). Dabei bezog es sich namentlich auf Lachat, der diesen Fall erwähnt, wobei dieser Autor unter "très peu de temps" ein oder zwei Tage versteht (David Lachat, Le bail à loyer, 2008, S. 672). Ob dies sodann auch gelten soll, wenn die Tilgung nicht durch Bezahlung sondern durch Verrechnungserklärung erfolgt, wird nicht abgehandelt.
Allein der Umstand, dass die gemahnten Beträge nur sehr kurze Zeit nach Ablauf der Zahlungsfrist getilgt wurden, macht eine vom Vermieter dennoch nach <ref-law> ausgesprochene Kündigung noch nicht rechtsmissbräuchlich. Andernfalls würde die gesetzlich bestimmte Nachfrist ihres Sinns entleert. Zu würdigen sind immer die besonderen Umstände des Einzelfalles. Zur nur sehr kurze Zeit nach Ablauf der Zahlungsfrist erfolgten Begleichung der Ausstände müssen weitere Umstände hinzutreten, welche die Kündigung des Vermieters als gegen Treu und Glauben verstossend erscheinen lassen, so etwa, dass der Mieter bis anhin stets pünktlich bezahlt hat oder der Ausstand sehr gering war. Derartige Umstände sind vorliegend nicht festgestellt. Namentlich ist der gemahnte Ausstand von Fr. 30'461.50 auch keineswegs gering. Die angebliche Verrechnungserklärung soll drei Tage nach Ablauf der Zahlungsfrist erfolgt sein, was kaum mehr als sehr kurze Zeit nach Ablauf der Zahlungsfrist bezeichnet werden kann. Bei dieser Sachlage kann der Beschwerdegegnerin nicht vorgeworfen werden, mit ihren Kündigungen vom 18. November 2008 gegen Treu und Glauben verstossen zu haben. Ob mit dem E-Mail vom 17. November 2008 überhaupt eine wirksame Verrechnungserklärung vorliegt, was das Mietgericht verneinte und das Obergericht offen liess, braucht demnach vorliegend nicht beurteilt zu werden.
4.4 Die Beschwerdeführer machen schliesslich ein widersprüchliches Verhalten der Beschwerdegegnerin geltend. Was sie zur Begründung vorbringen, ist nicht leicht nachzuvollziehen und erschöpft sich weitgehend in Hypothesen zur Interpretation der "Chronologie der Ereignisse". So wenn sie unterstellen, die Beschwerdegegnerin habe trotz den ausgesprochenen ordentlichen Kündigungen vom 18. September 2008 eigentlich das Mietverhältnis mit den Beschwerdeführern weiterführen wollen. Es sei nur darum gegangen, die Mieter unter Druck zu setzen, damit diese die zur Verrechnung erklärten Mietzinse doch noch bezahlten. Dazu sei die Androhung einer fristlosen Kündigung ein probates Druckmittel gewesen.
Aus dem Umstand, dass die Beschwerdegegnerin die ordentlichen Kündigungen vom 18. September 2008 nach der Schlichtungsverhandlung zurückzog, lässt sich kein widersprüchliches Verhalten ableiten. Es war ihr unbenommen, nach Erfüllung der diesbezüglichen Voraussetzungen die ausserordentlichen Kündigungen wegen Zahlungsverzugs durchzuziehen. Dass sie auf diesen Kündigungen bestand, zeigt zudem gerade, dass sie entgegen der Behauptung der Beschwerdeführer das Mietverhältnis mit ihnen nicht aufrecht erhalten wollte.
Unerfindlich ist schliesslich, inwiefern die Beschwerdeführer aus dem von ihnen im Weiteren angeführten E-Mail des Vertreters der Vermieterschaft vom 19. November 2008 ein widersprüchliches Verhalten der Beschwerdegegnerin ableiten könnten. Die darin geäusserte Bitte um Bestätigung, dass die Mietverhältnisse per Ende 2008 beendet seien, kann vielmehr ohne weiteres im Hinblick darauf gesehen werden, dass gegebenenfalls die anberaumte Schlichtungsverhandlung dahinfallen könnte. Wie dem auch sei, das Bundesgericht kann dieses E-Mail vom 19. November 2008 ohnehin nicht berücksichtigen, da sich diesbezüglich im angefochtenen Entscheid keine Feststellungen finden (vgl. Erwägung 2).
Nach dem Gesagten kann der Beschwerdegegnerin kein widersprüchliches Verhalten vorgeworfen werden, das die Kündigungen als missbräuchlich erscheinen liesse.
4.5 Die Kündigungen vom 18. November 2008 verstossen demnach nicht gegen <ref-law> und wurden von der Vorinstanz zutreffend als rechtsgültig beurteilt.
5. Aus diesen Gründen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Entsprechend dem Verfahrensausgang werden die Beschwerdeführer in 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. 8'000.-- werden den Beschwerdeführern auferlegt, in solidarischer Haftbarkeit.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 9'000.-- zu entschädigen, in solidarischer Haftbarkeit.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 17. Februar 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Widmer