Sachverhalt:
A. Im April 2004 schlossen B._ (Beschwerdeführer 2) und D._ als Mieter mit C._ (Beschwerdegegner) einen Mietvertrag über Geschäftsräumlichkeiten in Winterthur ab. Im September 2004 bat D._ den Beschwerdeführer 2, ihn aus dem Mietverhältnis zu entlassen. Mit undatiertem Vertrag mieteten sodann A._ (Beschwerdeführer 1) und der Beschwerdeführer 2 die Geschäftsräumlichkeiten. Mit Schreiben vom 16. März 2009 wurde dem Beschwerdeführer 2 unter Androhung der Kündigung nach <ref-law> eine letzte Zahlungsfrist für ausstehende Mietzinse der Monate Juli 2005 bis März 2009 in der Höhe von Fr. 545'500.-- angesetzt. Dieses Schreiben wurde in Kopie auch dem Beschwerdeführer 1 zugestellt. Am 22. April 2009 kündigte der Beschwerdegegner das Mietverhältnis mittels (separaten) amtlichen Formularen per 31. Mai 2009.
B. Die Beschwerdeführer räumten und verliessen die Mieträumlichkeiten bis zum Kündigungstermin nicht. Das daraufhin vom Beschwerdegegner im Juni 2009 gestellte Ausweisungsbegehren hiess das Bezirksgericht Winterthur gut. Das Obergericht des Kantons Zürich wies den Rekurs der Beschwerdeführer mit Beschluss vom 16. September 2009 ab, bestätigte den Entscheid des Bezirksgerichts und befahl den Beschwerdeführern, die Geschäftsräumlichkeiten unverzüglich zu räumen und zu verlassen. Das Kassationsgericht des Kantons Zürich trat auf die dagegen erhobene Nichtigkeitsbeschwerde am 15. Januar 2010 nicht ein.
C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht, den Beschluss des Obergerichts aufzuheben und das Ausweisungsbegehren abzuweisen. Das Bundesgericht erteilte der Beschwerde auf Antrag der Beschwerdeführer aufschiebende Wirkung.
Der Beschwerdegegner schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Nach <ref-law> beginnt die Beschwerdefrist, wenn der Entscheid eines oberen kantonalen Gerichts mit einem Rechtsmittel, das nicht alle Rügen nach den Artikeln 95-98 BGG zulässt, bei einer zusätzlichen kantonalen Gerichtsinstanz angefochten worden ist, erst mit der Eröffnung des Entscheids dieser Instanz. Mit der Beschwerde in Zivilsachen kann unter dieser Voraussetzung auch das Urteil der oberen kantonalen Instanz angefochten werden, soweit im Rahmen der Beschwerde in Zivilsachen zulässige Rügen dem höchsten kantonalen Gericht nicht unterbreitet werden konnten (<ref-ruling> E. 1.1 S. 93 f. mit Hinweis). Der Anhandnahme der Beschwerde steht mithin kein Fristablauf entgegen. Den Entscheid des Kassationsgerichts haben die Beschwerdeführer nicht angefochten. Der Beschluss des Obergerichts ist hinsichtlich sämtlicher Rügen, die an das Kassationsgericht hätten weitergezogen werden können bzw. wurden, nicht letztinstanzlich (<ref-law>; <ref-ruling> E. 1.3 S. 527 mit Hinweisen), weshalb auf entsprechende Rügen gegen den Entscheid des Obergerichts nicht einzutreten ist.
2. Ist der Mieter nach der Übernahme der Sache mit der Zahlung fälliger Mietzinse oder Nebenkosten im Rückstand, kann ihm der Vermieter 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 (<ref-law>). Bezahlt der Mieter innert der gesetzten Frist nicht, kann der Vermieter bei Wohn- und Geschäftsräumen mit einer Frist von mindestens 30 Tagen auf Ende eines Monats kündigen (<ref-law>).
2.1 Das Obergericht prüfte den Einwand der Beschwerdeführer, die seitens der Vertreterin des Beschwerdegegners von E._ und F._ unterzeichnete Zahlungsaufforderung sei nicht ordnungsgemäss erfolgt, da gemäss Handelsregisterauszug E._ kollektiv zeichne, während F._ nicht zeichnungsberechtigt sei. Das Obergericht erwog, die Unterschrift einer einzelnen Person sei ohne die verbindliche Mitwirkung der übrigen nicht verbindlich, wenn die Prokura mehreren Personen zu gemeinsamer Unterschrift erteilt worden sei. Habe jemand, ohne dazu ermächtigt zu sein, für den Vertretenen gehandelt, trete die Wirkung des rechtsgeschäftlichen Handelns für den Vertretenen nur dann ein, wenn er die Handlung genehmige. Die Genehmigung sei an keine Form gebunden und könne konkludent erfolgen. Der Beschwerdegegner selbst habe das Mietverhältnis mit separaten amtlichen Formularen vom 22. April 2009 gekündigt. Diese Kündigungsschreiben seien gestützt auf die vorangehende Zahlungsaufforderung ergangen. Die Kündigung sei wie folgt begründet worden: "Trotz Fristsetzung gemäss OR Art. 257d keine Mietzinszahlung eingegangen." Da der Beschwerdegegner die Kündigungen selbst unterzeichnet habe, könne ohne Weiteres auf eine konkludente Genehmigung der Zahlungsaufforderung vom 16. März 2009 nach <ref-law> geschlossen werden. Damit sei der Mangel der fehlenden Vollmacht geheilt, und die Ansetzung der Zahlungsfrist unter Androhung der Kündigung nach <ref-law> entfalte ihre Wirkung.
2.2 Die Beschwerdeführer machen geltend, Art. 32-40 OR bezögen sich nur auf den Abschluss von Verträgen. Da es sich bei der Kündigungsandrohung nach <ref-law> um eine einseitige Willenserklärung handle, gelange <ref-law> nicht zur Anwendung. Die Zahlungsfristansetzung genüge dem Formerfordernis der einfachen Schriftlichkeit nicht, so dass sie wirkungslos bleibe. Sollte die Rechtsauffassung der Vorinstanz zutreffen, sei zu beachten, dass der Vertretene erst mit der Genehmigung zum Ausdruck bringe, das Handeln des Vertreters nachträglich gutzuheissen und daran gebunden sein zu wollen. Der Beschwerdegegner habe die Zahlungsaufforderung demnach erst mit der Kündigung am 22. April 2009 genehmigt, weshalb die Kündigung vor Ablauf der Zahlungsfrist ausgesprochen worden und unwirksam sei.
2.3 Stellvertretung ist nicht nur bei Abschluss von Verträgen, sondern bei allen Rechtsgeschäften oder rechtsgeschäftsähnlichen Handlungen auf dem ganzen Gebiet des Zivilrechts möglich, soweit deren Gegenstand nicht höchstpersönlicher Natur ist (WATTER/SCHNELLER, in: Basler Kommentar, Obligationenrecht I, 4. Aufl. 2007, N. 3 ff. zu <ref-law>; ROGER ZÄCH, Berner Kommentar, 1990, N. 101 ff. der Vorbemerkungen zu Art. 32-40 OR; VON TUHR/PETER, Allgemeiner Teil des Schweizerischen Obligationenrechts, 3. Aufl. 1979, Bd. I, S. 351 f.). Die Anwendbarkeit von <ref-law> setzt so wenig wie <ref-law> einen Vertragsabschluss voraus. Mithin kann jedes einer Vertretung zugängliche und rechtserhebliche Verhalten genehmigt werden (ZÄCH, a.a.O., N. 31 zu <ref-law> und N. 103 ff. der Vorbemerkungen zu Art. 32-40 OR; WATTER/SCHNELLER, a.a.O., N. 2 zu <ref-law>; VON TUHR/PETER, a.a.O., S. 402). Problematisch ist die nachträgliche Genehmigung bei einseitigen Rechtsgeschäften, etwa bei Gestaltungsgeschäften. In der Lehre wird die Auffassung vertreten, dem Dritten dürfe nicht zugemutet werden, ein solches Geschäft entgegenzunehmen, wenn dessen Wirkung noch von der nachträglichen Genehmigung abhängig und diese ungewiss sei. Deshalb wird dem Dritten bei einseitigen, empfangsbedürftigen Rechtsgeschäften ein Rückweisungsrecht eingeräumt, wobei die Rückweisung sofort ausgesprochen werden muss. Erfolgt keine oder eine verspätete Rückweisung, befindet sich das einseitige Rechtsgeschäft in einem Schwebezustand, und es kann vom Vertretenen genehmigt oder verworfen werden (ROGER ZÄCH, a.a.O., N. 104 ff. der Vorbemerkungen zu Art. 32-40 OR). Jedenfalls hat die Genehmigung durch den Vertretenen zur Folge, dass das Rechtsgeschäft zwischen ihm und dem Dritten so abgeschlossen wird, wie es der Vertreter abgeschlossen hat. Entgegen der Auffassung der Beschwerdeführer wirkt die Genehmigung - eine anderslautende Parteivereinbarung vorbehalten - rückwirkend auf den Zeitpunkt des Geschäftsabschlusses (WATTER/SCHNELLER, a.a.O., N. 8 zu <ref-law>).
2.4 Sinn der Ansetzung einer Zahlungsfrist nach <ref-law> ist es, dem Mieter eine letzte Gelegenheit einzuräumen, den schwerwiegenden Folgen einer ausserordentlichen Kündigung zu entgehen und dem Vermieter eine klare Wahlmöglichkeit betreffend das weitere Vorgehen einzuräumen (PETER HIGI, Zürcher Kommentar, 1994, N. 31 zu <ref-law> mit Hinweisen). Diese Vorgehensweise sichert die Erfüllung der gesetzlichen Voraussetzung für die Berechtigung zur ausserordentlichen Kündigung (HIGI, a.a.O., N. 57 zu <ref-law>). Wenn die gesetzlichen oder vertraglichen Voraussetzungen einer ausserordentlichen Kündigung nicht erfüllt sind, ist die Kündigung unwirksam (<ref-ruling> E. 1c/aa S. 161).
2.5 Die Zahlungsfrist muss von einer dazu berechtigten Person angesetzt werden. Ist die notwendige Genehmigung oder Zustimmung eines zweiten kollektiv Unterschriftsberechtigten noch nicht erfolgt, entfaltet die Zahlungsaufforderung grundsätzlich keine Wirkung, wenn für den Mieter unklar bleibt, ob die Androhung der Kündigung bei Nichteinhalten der Frist tatsächlich gilt. Nach dem Willen des Gesetzgebers soll dem Mieter von Wohn- und Geschäftsräumen eine Zahlungsfrist von mindestens 30 Tagen zur Verfügung stehen, um ausstehende Mietzinse oder Nebenkosten zu begleichen. Eine diesbezügliche Unsicherheit bzw. ein Schwebezustand bis zu einer Genehmigung ist an sich nicht zumutbar (vgl. Zäch, a.a.O., N. 104 der Vorbemerkungen zu Art. 32-40 OR), sofern im Zeitpunkt der Genehmigung nicht noch mindestens 30 Tage verbleiben. Von einer Unsicherheit über die Gültigkeit der Zahlungsaufforderung mit Kündigungsandrohung bzw. einem Schwebezustand kann allerdings nur gesprochen werden, wenn der Mieter tatsächlich an deren Verbindlichkeit zweifelt. Wird der Mangel geheilt, bevor der Mieter diesen bemerkt, bestand von seiner Seite nie Unsicherheit über die Wirksamkeit der Zahlungsaufforderung (vgl. analog <ref-ruling> E. 2b S. 135 f. zur Kündigung eines Arbeitsverhältnisses). Unter diesen Voraussetzungen besteht mit Blick auf den Gesetzeszweck kein Anlass, die Zahlungsaufforderung mit Kündigungsandrohung trotz der nachträglichen Genehmigung als ungültig zu erachten.
2.6 Dass die fehlende Zweitunterschrift im Zeitpunkt der Zahlungsaufforderung zu einer Ungewissheit für die Beschwerdeführer führte, ist den für das Bundesgericht grundsätzlich massgebenden Feststellungen der Vorinstanz (<ref-law>) nicht zu entnehmen. Die Beschwerdeführer zeigen auch nicht auf, im kantonalen Verfahren prozesskonform entsprechende Behauptungen aufgestellt zu haben. Eine Sachverhaltsergänzung scheidet somit aus. Damit durfte das Obergericht bundesrechtskonform davon ausgehen, in der vom Beschwerdegegner selbst unterzeichneten Kündigung liege eine Genehmigung, womit der Mangel geheilt sei. Die Rüge erweist sich als unbegründet.
3. Bezüglich der Höhe des in der Zahlungsaufforderung angegebenen Mietzinsausstands anerkennen die Beschwerdeführer die Richtigkeit der vor erster Instanz eingereichten Forderungszusammenstellung des Beschwerdegegners. Sie bestreiten jedoch, dass sie dem Beschwerdegegner zum Zeitpunkt der Fristansetzung tatsächlich Fr. 545'000.-- an Mietzinsausständen schuldig gewesen seien.
3.1 Im Zusammenhang mit der Frage, ob der in der Zahlungsaufforderung enthaltene Betrag an ausstehenden Mietzinsen Juli 2005 bis März 2009 von Fr. 545'000.-- den tatsächlichen Mietzinsausständen entspreche, hielt die Vorinstanz hinsichtlich des von Hand auf der Forderungszusammenstellung des Beschwerdegegners angebrachten Vermerks "15'000.-- bar" fest, die Beschwerdeführer behaupteten erstmals, dass es sich dabei um eine weitere Mietzinszahlung handle. Aus den Akten gehe nicht hervor, ob dies zutreffe. Die nicht weiter belegte, pauschale Behauptung der Beschwerdeführer, sie hätten Fr. 15'000.-- bar an die Mietzinsen bezahlt, sei haltlos und aufgrund der Verspätung im Rekursverfahren unbeachtlich. Im Übrigen wäre davon auszugehen, dass die Einzahlung von Fr. 15'000.-- nach Verfassen der Zahlungsaufforderung geschehen sei, was deren Gültigkeit nicht beeinträchtige.
3.2 Die Beschwerdeführer weisen darauf hin, sie hätten bereits vor erster Instanz geltend gemacht, dem Beschwerdegegner (im Jahr 2005) Barzahlungen geleistet zu haben. Soweit sie damit sinngemäss eine Verletzung des rechtlichen Gehörs rügen oder geltend machen wollten, die Vorinstanz hätte ihr Vorbringen zu Unrecht als unzulässiges Novum behandelt, ist auf ihre Rüge nicht einzutreten, da sie diese bereits vor dem Kassationsgericht erhoben und dessen Entscheid nicht angefochten haben (vgl. E. 1). Dasselbe gilt für das Vorbringen der Beschwerdeführer, die Erwägung des Obergerichts, die Zahlung von Fr. 15'000.-- sei erst nach dem Erstellen der Zahlungsaufforderung bzw. der Zahlungsfristansetzung vom 16. März 2009 erfolgt, sei "unhaltbar, durch nichts belegt und klar aktenwidrig".
3.3 Das Obergericht hielt fest, gehe man von der Zusammenstellung der Nebenkosten im Mietvertrag aus, ergäben sich tatsächlich monatliche Nebenkosten von Fr. 416.65. Ausgehend vom aufgeführten Jahresmietzins von Fr. 209'000.-- würde der monatliche Bruttomietzins Fr. 17'416.65 betragen. Im Vertrag sei hingegen ein monatlich zahlbarer Betrag von Fr. 17'450.-- festgelegt worden. Für die Beschwerdeführer sei der monatliche Bruttomietzins klar ersichtlich, und sie seien damit einverstanden gewesen. Überdies hätten sie diesen bereits mehrmals bezahlt. Die Berufung auf zu hohe Nebenkosten nach knapp fünf Jahren sei als rechtsmissbräuchlich zu qualifizieren.
3.4 Die Beschwerdeführer bringen vor, bei der Berechnung des Bruttomietzinses von Fr. 17'450.-- im Mietvertrag handle es sich offensichtlich um einen Berechnungsfehler, der nach <ref-law> zu korrigieren sei. Der Vertragswille der Parteien habe sich auf einen monatlichen Bruttomietzins von Fr. 17'416.65 bezogen. Die Nebenkosten und somit der monatliche Bruttomietzins sei in der Forderungszusammenstellung des Beschwerdegegners zu hoch und damit falsch berechnet. Die Rückforderung hinsichtlich zu viel bezahlter Nebenkosten verjähre absolut nach zehn Jahren. Solange die Verjährung nicht eingetreten sei, sei eine Berufung auf zu hoch angesetzte Nebenkosten nicht rechtsmissbräuchlich.
3.5 Die Geltendmachung einer Forderung innerhalb der Verjährungsfrist ist in der Tat nur rechtsmissbräuchlich, wenn besondere Umstände hinzukommen; andernfalls würde das Rechtsinstitut der Verjährung weitgehend ausgehöhlt (<ref-ruling> E. 2 S. 431; <ref-ruling> E. 2 S. 275). Solche Umstände lassen sich dem angefochtenen Entscheid nicht entnehmen. Zu beurteilen ist jedoch nur, ob die Zahlungsaufforderung gültig ist. Die Zahlungsaufforderung des Vermieters nach <ref-law> muss den Ausstand nicht zwingend ziffernmässig bezeichnen. Es ist erforderlich, aber auch ausreichend, dass der Zahlungsrückstand einwandfrei bestimmbar ist (Urteil 4C.123/2000 vom 14. Juni 2000 E. 3b, teilweise wiedergegeben in MRA 2001 S. 47; vgl. dazu Roger Weber, in: Basler Kommentar, Obligationenrecht I, 4. Aufl. 2007, N. 4 zu <ref-law>).
3.5.1 Gemäss <ref-law> hindern blosse Rechnungsfehler die Verbindlichkeit des Vertrags nicht, sind aber zu berichtigen. Ein allfälliger Rechnungsfehler beträfe den Mietvertrag selbst und nur mittelbar den in der Zahlungsaufforderung angeführten Betrag. Es ist jedoch weder festgestellt noch wird von den Beschwerdeführern geltend gemacht, sie hätten sich vor der Zahlungsaufforderung gegen den im Vertrag eingesetzten Betrag zur Wehr gesetzt. Somit kann es dem Vermieter nicht schaden, wenn er bei der Zahlungsaufforderung vom Mietzins, der tatsächlich bezahlt wird, ausgeht. Ein von beiden Parteien bisher nicht entdeckter Fehler bei der Mietzinsfestsetzung kann nicht zur Ungültigkeit der Zahlungsaufforderung führen. Wenn nur der Mieter den Fehler bezüglich der Festsetzung des Mietzinses erkennt, ist er - im Gegensatz zum Vermieter - in der Lage, den Ausstand korrekt zu berechnen. Soweit der Mieter aus einem allfälligen Fehler etwas zu seinen Gunsten ableiten will, darf er die Zahlungsfrist nicht einfach verstreichen lassen, ohne den Vermieter auf den Fehler bei der Mietzinsfestsetzung hinzuweisen. Nach dem Willen des Gesetzgebers soll das Problem von ausstehenden Mietzinsen oder Nebenkosten bei Wohn- und Geschäftsräumen innert 30 Tagen bereinigt werden. Macht der Mieter geltend, der Mietzins oder die Nebenkosten seien wegen eines Rechnungsfehlers zu hoch, muss er dies innerhalb dieser Frist tun und die verbleibenden Ausstände, soweit sie trotz eines Rechnungsfehlers bestehen, begleichen. Will der Mieter die Verrechnung mit zu viel bezahlten Mietzinsen erklären, hat er dies ebenfalls während der Zahlungsfrist zu tun (<ref-ruling> E. 6b/bb S. 248, bestätigt in Urteil 4C.174/1999 vom 14. Juli 1999 E. 2b, publ. in SJ 2000 I 78).
3.5.2 Dasselbe gilt soweit die Beschwerdeführer geltend machen, die mittels Staffelung vereinbarten Mietzinserhöhungen seien nicht mit dem amtlichen Formular angezeigt worden, was zu deren Nichtigkeit führe und der Vorinstanz in diesem Zusammenhang eine Verletzung des Grundsatzes "negativa non sunt probanda" sowie von <ref-law> vorwerfen. Auch diese Vorbringen betreffen primär die Höhe des geschuldeten Mietzinses und nur mittelbar den in der Zahlungsaufforderung angegebenen Betrag. Da nicht festgestellt ist, dass die Beschwerdeführer vor der Zahlungsaufforderung den vom Vermieter verlangten Mietzins je beanstandeten, kann allein die Tatsache, dass der Vermieter den bisher unangefochtenen Mietzins der Zahlungsaufforderung zugrunde legte, nicht zu deren Ungültigkeit führen. Im Übrigen erachtete das Obergericht die Vorbringen der Beschwerdeführer, die Anzeigen seien nicht erfolgt, als verspätet und daher unbeachtlich. Sollte dies nicht zutreffen, hätten die Beschwerdeführer diese Rügen beim Kassationsgericht erheben bzw. dessen Entscheid anfechten müssen (vgl. E. 1).
3.5.3 Wie zu entscheiden wäre, wenn sich nachträglich herausstellt, dass unter Berücksichtigung der Nichtigkeit einer Mietzinsanpassung oder eines allfälligen Rechnungsfehlers tatsächlich nie ein Zahlungsrückstand bestand, braucht nicht entschieden zu werden, weil Entsprechendes nicht festgestellt ist und von den Beschwerdeführern nicht behauptet wird. Damit ist nicht zu beanstanden, dass die Vorinstanz die Gültigkeit der Zahlungsaufforderung bejahte.
4. Insgesamt ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

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