Sachverhalt:
A. Die Y._ System AG, Rechtsvorgängerin der Y._ AG (nachfolgend: Beschwerdegegnerin), mietete bei X._ (nachfolgend: Beschwerdeführer) mit Vertrag vom 17. November 2000 Büro- und Gewerbeflächen zu einem monatlichen Mietzins von Fr. 59'000.-- sowie 5'000.-- Nebenkosten.
B. Mit Zahlungsbefehl Z._ Nr. 1 vom 23. Mai 2007 betrieb der Beschwerdeführer die Beschwerdegegnerin auf Bezahlung ausstehender Mietzinse von insgesamt Fr. 96'936.-- nebst 6% Zins seit 1. Juni 2006 und verlangte mit Eingabe vom 18. Juni 2007 provisorische Rechtsöffnung für einen "Teilbetrag von Fr. 45'936.-- nebst Zins von 5% seit 23. Mai 2007 sowie für Fr. 100.-- Zahlungsbefehlskosten", eventualiter für Fr. 5'936.-- nebst 5% Zins seit genanntem Datum und Fr. 60.-- Zahlungsbefehlskosten.
Mit Verfügung vom 27. August 2007 wies der Einzelrichter Z._ das Rechtsöffnungsbegehren ab.
C. Gegen diese Verfügung führte der Beschwerdeführer am 18. September 2007 Rekurs beim Kantonsgericht Schwyz. Mit Beschluss RK2 2007 117 vom 26. Mai 2008 wies das Kantonsgericht den Rekurs ab, soweit es darauf eintrat.
D. Im Nachgang zur einzelrichterlichen Verfügung vom 27. August 2007 liess der Beschwerdeführer am 6./9. November 2007 gegen die Beschwerdegegnerin ein Retentionsverzeichnis errichten, und zwar für fällige Mietzinse vom 1. November 2006 bis 31. Oktober 2007 (Fr. 136'946.--) sowie laufende Zinse vom 1. November 2007 bis 30. April 2008 (Fr. 376'086.--).
Mit Zahlungsbefehl Nr. 2 vom 21. November 2007 betrieb der Beschwerdeführer die Beschwerdegegnerin auf Pfandverwertung für eine Forderung von Fr. 136'946.-- nebst Zins zu 5% seit 1. November 2007, Betreibungs- und Retentionskosten von Fr. 441.-- sowie Zahlungsbefehlskosten von Fr. 200.--. Dagegen erhob die Beschwerdegegnerin am 23. November 2007 Rechtsvorschlag.
E. Am 3. Januar 2008 ersuchte der Beschwerdeführer den Einzelrichter des Bezirksgerichts Z._ um Erteilung der provisorischen Rechtsöffnung für den Betrag von Fr. 136'946.-- zuzüglich Zins zu 5% seit 1. November 2007, Retentionskosten von Fr. 441.-- sowie Zahlungsbefehlskosten von Fr. 200.--.
Mit Verfügung vom 31. März 2008 erteilte der Einzelrichter provisorische Rechtsöffnung für einen Forderungsanteil von Fr. 96'000.-- nebst Zins zu 5% seit 1. November 2007, Zahlungsbefehlskosten von Fr. 200.-- sowie Retentionskosten von Fr. 441.--.
F. Dagegen erhob die Beschwerdegegnerin am 18. April 2008 Rekurs und beantragte die Abweisung des Rechtsöffnungsbegehrens, soweit darauf einzutreten sei, eventualiter die Zurückweisung an die erste Instanz zu neuer Beurteilung.
Mit Beschluss RK2 2008 35 vom 4. März 2009 hiess das Kantonsgericht Schwyz den Rekurs gut und wies das Rechtsöffnungsbegehren des Beschwerdeführers ab.
G. Mit Beschwerde vom 22. April 2009 beantragt der Beschwerdeführer dem Bundesgericht die Aufhebung des kantonsgerichtlichen Beschlusses und die Erteilung der provisorischen Rechtsöffnung für den Betrag von Fr. 96'000.--.
Das Kantonsgericht schliesst in seiner Vernehmlassung vom 16. September 2009 auf Abweisung der Beschwerde, die Beschwerdegegnerin in ihrer Vernehmlassung vom 1. Dezember 2009 auf Abweisung, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid (Art. 75 Abs. 1 BGG) betreffend ein Rechtsöffnungsbegehren, somit in einer Schuldbetreibungs- und Konkurssache (Art. 72 Abs. 2 lit. a BGG), welcher einen Endentscheid darstellt (Art. 90 BGG). Der Streitwert von Fr. 30'000.-- (Art. 74 Abs. 1 lit. b BGG) ist offensichtlich überschritten. Insofern ist die Beschwerde in Zivilsachen zulässig.
1.2 Die Beschwerde kann wegen Verletzung von schweizerischem Recht gemäss Art. 95 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es kann die Verletzung von Grundrechten und von kantonalem Recht nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG).
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Der Beschwerdeführer kann die Feststellung des Sachverhalts rügen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2 S. 252). Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss rechtsgenüglich darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss Art. 105 Abs. 2 BGG gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre; andernfalls kann ein Sachverhalt, der vom im angefochtenen Entscheid festgestellten abweicht, nicht berücksichtigt werden. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3 S. 351, 393 E. 7.1 S. 398, 462 E. 2.4 S. 466 f.).
2. 2.1 Beruht die Forderung auf einer durch öffentliche Urkunde festgestellten oder durch Unterschrift bekräftigten Schuldanerkennung, so kann der Gläubiger die provisorische Rechtsöffnung verlangen (Art. 82 Abs. 1 SchKG). Der Richter spricht dieselbe aus, sofern der Betriebene nicht Einwendungen, welche die Schuldanerkennung entkräften, sofort glaubhaft macht (Art. 82 Abs. 2 SchKG).
2.2 Eine Schuldanerkennung im Sinn von Art. 82 Abs. 1 SchKG liegt vor, wenn daraus der vorbehalts- und bedingungslose Wille des Betriebenen hervorgeht, dem Betreibenden eine bestimmte oder leicht bestimmbare Geldsumme zu zahlen (<ref-ruling> E. 4.1 S. 480 f.). Im Rahmen des Rechtsöffnungsverfahrens prüft der Richter lediglich die Beweiskraft des Rechtsöffnungstitels, nicht die materielle Gültigkeit der Forderung (<ref-ruling> E. 4.1.1 S. 142). Das Verfahren der provisorischen Rechtsöffnung ist ein Urkundenprozess, bei dem es nicht darum geht, über den Bestand der in Betreibung gesetzten Forderung, sondern über das Vorliegen eines Rechtsöffnungstitels zu befinden (<ref-ruling> E. 4.1.1 S. 142; vgl. auch <ref-ruling> E. 1.5 S. 400). Die provisorische Rechtsöffnung ist nur dann zu erteilen, wenn der im Verfahren geltend gemachte Anspruch durch die dem Rechtsöffnungsrichter vorgelegten Dokumente in jeder Hinsicht ausgewiesen ist, nicht bereits dann, wenn er lediglich als wahrscheinlich erscheint (Urteil 5A_351/2007 vom 30. August 2007 E. 5; Peter Stücheli, Die Rechtsöffnung, 2000, S. 326).
3. Das Kantonsgericht führte aus, die Beschwerdegegnerin sei im erstinstanzlichen Verfahren mit der Klageantwort säumig geblieben, weshalb der Einzelrichter, in Abweichung von seiner Verfügung in der vorangegangenen Betreibung, auf die Angaben des Beschwerdeführers abgestellt habe. Die Beschwerdegegnerin bringe u.a. formelle Einreden vor, insbesondere die Rüge, nicht gehört worden zu sein, indem der Einzelrichter sie selbst anstelle ihrer Rechtsvertreterin zur (versäumten) Klageantwort eingeladen habe, womit die Zustellungsvorschriften, namentlich § 113 der Gerichtsordnung des Kantons Schwyz vom 10. Mai 1974 (GO/SZ; SRSZ 231.110), verletzt worden seien. Indes habe sie es versäumt, innert gesetzlicher Frist ein Wiederherstellungsgesuch i.S.v. § 129 GO/SZ einzureichen oder mit ihrem Rekurs zu verbinden.
Weiter hielt das Kantonsgericht fest, dass die Beschwerdegegnerin zweitinstanzlich zur Hauptsache geltend mache, es liege kein zureichender Rechtsöffnungstitel für die Betreibungsforderung vor und das Vorgehen des Beschwerdeführers sei rechtsmissbräuchlich.
Es erwog, dass sich der Beschwerdeführer im Verfahren RK2 2007 117 selbst auf Zusatzvereinbarungen zum Mietvertrag berufen habe. Aus diesen folge, dass ein reduzierter monatlicher Mietzins bis zum Jahr 2011 von Fr. 56'000.-- vereinbart worden sei, wobei noch "Rückvergütungen" in der Höhe von monatlich Fr. 6'000.-- ab Januar 2006 sowie Fr. 5'000.-- ab Juni 2006 zugestanden worden seien. Dies sei auch der ersten Instanz aus dem früheren Verfahren bekannt gewesen. Unter diesen Umständen sei nicht mehr anzunehmen, der ursprüngliche, mehrfach abgeänderte und hier einzig angerufene Mietvertrag stelle noch eine gültige Schuldanerkennung dar. Vielmehr erscheine es als rechtsmissbräuchlich, dass der Beschwerdeführer versuche, gestützt auf eine nicht mehr aktuelle Urkunde Rechtsöffnung zu erwirken, ohne die im vorgängigen Verfahren anerkannten Abänderungsdokumente einzulegen oder auch nur zu erwähnen. Selbst aber wenn ein Grundtitel noch bejaht werden könnte, sei aus dem früheren Verfahren unabhängig von der erstinstanzlichen Säumnis der Beschwerdegegnerin abzuleiten, dass keine monatlich über Fr. 51'000.-- (bzw. Fr. 50'000.--) liegende Schuldanerkennung liquid ausgewiesen sei, weshalb die Rechtsöffnung auch unter diesem Aspekt zu verweigern sei.
Damit liess das Kantonsgericht die Frage ausdrücklich offen, ob aufgrund der vorliegenden Umstände die zweimalige Anhebung der Betreibung ausschliesslich zum Zweck gehabt habe, den Betriebenen zu bedrängen, und daher nichtig sei, wobei es dies als fraglich bezeichnete.
4. 4.1 Der Beschwerdeführer rügt vor Bundesgericht, das Kantonsgericht stütze seinen Entscheid einzig auf Einwendungen der Beschwerdegegnerin, welche diese erst vor zweiter Instanz erhoben habe, was gegen Art. 82 Abs. 2 SchKG verstosse und daher unzulässig sei.
Er beruft sich dabei auf die Lehrmeinung von Staehelin, wonach der Schuldner seine Einwendungen sofort glaubhaft machen müsse, Einwendungen in einem Beschwerdeverfahren daher verspätet seien und von Bundesrechts wegen nicht gehört werden dürften (Daniel Staehelin, in: Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, Bd. I, 1998, N. 86 zu Art. 82 SchKG).
4.2 Dabei verkennt der Beschwerdeführer, dass sich gemäss ständiger Rechtsprechung des Bundesgerichts nach kantonalem Recht entscheidet, ob im kantonalen Rechtsmittelverfahren gegen Rechtsöffnungsentscheide Noven eingereicht werden können (Urteile 5D_147/2009 vom 11. November 2009 E. 3.2 in fine; 5A_240/2009 vom 10. Juli 2009 E. 3.3.2; so bereits <ref-ruling> E. 1 S. 91; für die definitive Rechtsöffnung Urteile 5P.31/2002 vom 22. März 2002 E. 4; P.673/1960 vom 25. Januar 1961 E. 2, in: JdT 1961 II S. 92; vgl. auch Pierre-Robert Gilliéron, Commentaire de la loi fédérale sur la poursuite pour dettes et la faillite, Premier volume, 1999, N. 109 zu Art. 82 SchKG, N. 96 zu Art. 84 SchKG). Daher erweist sich seine Rüge, das Kantonsgericht habe in seinem Entscheid zu Unrecht die zweitinstanzlich erhobenen Einwendungen der Beschwerdegegnerin berücksichtigt, als unbegründet: Bundesrecht ist dadurch nicht verletzt, und eine willkürliche Anwendung von kantonalem Recht wird nicht gerügt.
Der Beschwerdeführer macht geltend, die Akten RK2 2007 117, auf die das Kantonsgericht (s. oben, E. 3) wie auch die Beschwerdegegnerin in ihrem Rekurs vom 18. April 2008 Bezug genommen haben, beträfen - wie er bereits in seiner Rekursantwort vom 26. Mai 2008 ausgeführt habe - eine andere Betreibung und seien im vorliegenden Verfahren nicht beizuziehen. Indes tut er auch in diesem Zusammenhang nicht dar, weshalb der Beizug dieser Akten in prozessualer Hinsicht unzulässig gewesen sein und insbesondere eine willkürliche Anwendung von kantonalem Recht darstellen soll. Dieser Einwand ist daher ebenfalls unbegründet.
5. 5.1 In der Sache macht der Beschwerdeführer geltend, das Kantonsgericht habe aktenwidrig und willkürlich angenommen, er habe sich selbst in einem anderen Verfahren auf Zusatzvereinbarungen zum Mietvertrag berufen, aus welchen folge, dass ein reduzierter monatlicher Mietzins bis zum Jahr 2011 von Fr. 56'000.-- vereinbart worden sei, und habe diese anerkannt.
Tatsächlich habe die Beschwerdegegnerin das Dokument eingereicht und sich darauf berufen, während er dessen Gültigkeit ausdrücklich bestritten und dieses als irrelevant bezeichnet habe, weshalb ihm auch kein rechtsmissbräuchliches Verhalten vorgeworfen werden könne. So habe er bereits vor Kantonsgericht geltend gemacht, die Reduktion des Mietzinses habe gemäss Schreiben vom 7. November 2003 nur für das Jahr 2004 gegolten; eine Reduktion für längere Zeit sei nicht vereinbart worden. Sein Schreiben vom 31. Oktober 2005 sei nur ein mit Bedingungen versehenes Angebot an die Beschwerdegegnerin gewesen, welches diese nicht angenommen habe, was aus deren Schreiben vom 2. November 2005 hervorgehe, welches er als urkundlichen Beweis eingereicht habe. Somit sei der Mietvertrag vom 17. November 2000 durch dieses Schreiben nicht abgeändert worden. Ausserdem habe er in seiner Rekursantwort geltend gemacht, dass auch das Schreiben vom 7. Februar 2006 (...) den Mietvertrag nicht abgeändert habe, zumal dieses form- und fristgerecht wegen Grundlagenirrtums angefochten worden sei, was die Beschwerdegegnerin bestätige. Diese Einwendungen habe die Vorinstanz ausser Acht gelassen.
5.2 Wie bereits dargelegt, hielt das Kantonsgericht jedoch ausdrücklich fest, der Beschwerdeführer habe sich selbst auf Zusatzvereinbarungen zum Mietvertrag berufen, aus welchen eine Reduktion des Mietzinses hervorgehe, sodass der ursprüngliche Mietvertrag keine gültige Schuldanerkennung mehr darstelle, jedenfalls damit aber keine monatlich über Fr. 51'000.-- (bzw. Fr. 50'000.--) liegende Schuldanerkennung liquid ausgewiesen sei (s. oben, E. 3). Damit hat es die Einwände des Beschwerdeführers, entgegen seinen Ausführungen, nicht ausser Acht gelassen, sondern verworfen. Insofern geht der Vorwurf der Aktenwidrigkeit an der vorinstanzlichen Argumentation vorbei, sodass darauf nicht einzutreten ist.
5.3 Was die Mietzinsreduktion betrifft, macht der Beschwerdeführer vor Bundesgericht lediglich geltend, er habe Dokumente eingereicht, aus welchen seiner Ansicht nach hervorgehen soll, dass er diese nur offeriert bzw. wegen Grundlagenirrtums angefochten habe (s. oben, E. 5.1). Er rügt in allgemeiner Weise, es sei völlig unerfindlich, wie die Vorinstanz den Schluss ziehen könne, dass keine monatlich über Fr. 51'000.-- (bzw. Fr. 50'000.--) liegende Schuldanerkennung liquid ausgewiesen sei, bezieht sich in diesem Zusammenhang ausschliesslich auf die Begründung im erstinstanzlichen Entscheid und tut nicht dar, weshalb das Kantonsgericht davon hätte ausgehen sollen, es liege eine Schuldanerkennung vor, aus welcher der vorbehalts- und bedingungslose Wille der Beschwerdegegnerin hervorgehe, ihm eine bestimmte oder leicht bestimmbare Geldsumme zu zahlen (s. oben, E. 2.2). Ausserdem ist aus diesen Äusserungen nicht ersichtlich, ob der Beschwerdeführer sich gegen die vorinstanzlichen Sachverhaltsfeststellungen richten oder die Anwendung des falschen Beweismasses (s. oben, E. 2.2) rügen will. Letzteres würde jeglicher Begründung entbehren. Sind die betreffenden Vorbringen hingegen als Sachverhaltsrügen aufzufassen, bleibt festzuhalten, dass nicht einmal eine als verletzt zu betrachtende Norm des schweizerischen Rechts genannt wird (vgl. Art. 97 Abs. 1 i.V.m. Art. 95 BGG; s. oben, E. 1.3) und dass die Ausführungen in der Beschwerdeschrift nicht über eine appellatorische Kritik hinausgehen. Damit ist auf die Rüge nicht einzutreten.
6. Zusammenfassend ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Gemäss dem Ausgang dieses Verfahrens wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1, Art. 68 Abs. 1 und Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Kantonsgericht des Kantons Schwyz, 2. Rekurskammer, schriftlich mitgeteilt.
Lausanne, 25. Januar 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Rapp