Sachverhalt:
A. Mit Zahlungsbefehl vom 26. Oktober 2006 betrieb die X._ AG (nachfolgend: Beschwerdeführerin) die Y._ AG (nachfolgend: Beschwerdegegnerin) auf Verwertung eines Faustpfandes für eine Forderung von Fr. 11'208.50 zuzüglich Zins von 5 % seit 1. Oktober 2006 und Kosten der Aufnahme des Retentionsverzeichnisses von Fr. 148.-- sowie Kosten des Zahlungsbefehls von Fr. 100.--. Gegen die Betreibung erhob die Beschwerdegegnerin am 13. November 2006 Rechtsvorschlag.
B. Mit Eingabe vom 17. November 2006 verlangte die Beschwerdeführerin in dieser Betreibung beim Bezirksgericht Zürich provisorische Rechtsöffnung für die Forderungssumme von Fr. 11'208.50 zuzüglich Zins von 5 % seit 1. Oktober 2006 und Betreibungskosten von Fr. 256.-- sowie die Feststellung des Retentionsrechts gemäss Retentionsverzeichnis. Mit Verfügung vom 5. Februar 2007 erteilte die Einzelrichterin des Bezirksgerichts Zürich für Zins zu 5 % auf Fr. 5'826.80 für die Zeit vom 1. bis zum 13. Oktober 2006 sowie für Fr. 5'381.70 nebst Zins zu 5 % seit 1. Oktober 2006, Fr. 123.-- Retentions- und Fr. 78.-- Betreibungskosten provisorische Rechtsöffnung. Im Mehrbetrag wurde das Begehren abgewiesen.
C. Am 21. Februar 2007 erhob die Beschwerdeführerin beim Obergericht des Kantons Zürich Nichtigkeitsbeschwerde gegen den Rechtsöffnungsentscheid und verlangte dessen Aufhebung insofern, als dem Rechtsöffnungbegehren nicht entsprochen worden war, und die Erteilung der Rechtsöffnung für diesen Teil. Eventualiter stellte sie das Begehren um eine entsprechende Anweisung des Bezirksgerichts.
Mit Beschluss des Obergerichts vom 30. März 2007 wurde die Nichtigkeitsbeschwerde abgewiesen.
D. Die Beschwerdeführerin hat beim Bundesgericht am 16. Mai 2007 Beschwerde in Zivilsachen mit dem Antrag eingereicht, den obergerichtlichen Beschluss sowie die Verfügung der Einzelrichterin des Bezirksgerichts Zürich aufzuheben, ihr auch für den Betrag von Fr. 5'826.80 zuzüglich Zins von 5 % seit 14. Oktober 2006 sowie die weiteren Betreibungskosten von Fr. 55.-- provisorische Rechtsöffnung zu erteilen und - sinngemäss - das Retentionsrecht gemäss Retentionsverzeichnis festzustellen. Die Beschwerdegegnerin schliesst in ihrer Vernehmlassung vom 15. Januar 2008 auf Abweisung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid in Schuldbetreibungs- und Konkurssachen (Art. 72 Abs. 2 lit. a, Art. 75 Abs. 1 BGG). Soweit die Beschwerdeführerin Rügen vorbringt, welche das Obergericht nicht oder mit engerer Kognition als das Bundesgericht geprüft hat, ficht sie in ihren Rechtsbegehren sowie in der Beschwerdebegründung zu Recht den erstinstanzlichen Entscheid mit an (sog. Dorénaz-Praxis, vgl. <ref-ruling> E. 2 mit Hinweisen).
Der notwendige Streitwert von Fr. 30'000.-- gemäss <ref-law> ist offensichtlich nicht erreicht. Daher sind die sich insbesondere gegen den mitangefochtenen erstinstanzlichen Entscheid richtenden materiellrechtlichen Rügen nur umfassend zu prüfen, wenn sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt (Art. 74 Abs. 2 lit. a i.V.m. Art. 95 und Art. 106 Abs. 1 BGG).
1.2 Der Begriff der Rechtsfrage von grundsätzlicher Bedeutung ist restriktiv auszulegen (<ref-ruling> E. 1.1 S. 495). Insbesondere ist erforderlich, dass die zu beurteilende Frage von allgemeiner Tragweite ist (Urteil 5A_125/2007 vom 20. September 2007, E 2.2.2; vgl. auch <ref-ruling> E. 1.2 S. 495 f.). Dabei hat die Beschwerdeführerin darzulegen, inwiefern sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt (<ref-ruling> E. 2.4 S. 648).
Gemäss den für das Bundesgericht verbindlichen (<ref-law>) Sachverhaltsfeststellungen des Obergerichts haben die Parteien für die Dauer bis zum 31. März 2009 einen Mietvertrag abgeschlossen und hat die Beschwerdegegnerin (als die Mieterin) das Mietobjekt Ende November 2006 verlassen sowie der Beschwerdeführerin die Schlüssel zukommen lassen. Der von der Beschwerdeführerin geltend gemachte Betrag betrifft die Restforderung eines Mietzinses.
Gibt der Mieter die Sache zurück, ohne Kündigungsfrist oder -termin einzuhalten, so ist er von seinen Verpflichtungen gegenüber dem Vermieter nur befreit, wenn er einen für den Vermieter zumutbaren neuen Mieter vorschlägt; dieser muss zahlungsfähig und bereit sein, den Mietvertrag zu den gleichen Bedingungen zu übernehmen (<ref-law>). Andernfalls muss er den Mietzins bis zu dem Zeitpunkt leisten, in dem das Mietverhältnis gemäss Vertrag oder Gesetz endet oder beendet werden kann (<ref-law>). Der Vermieter muss sich anrechnen lassen, was er an Auslagen erspart und durch anderweitige Verwendung der Sache gewinnt oder absichtlich zu gewinnen unterlassen hat (<ref-law>).
Entgegen der Ansicht der Beschwerdeführerin ist nicht grundsätzlich zu entscheiden, ob der Anspruch nach <ref-law> als vertraglicher Erfüllungsanspruch oder als gesetzliche Ersatzpflicht zu qualifizieren ist. Vielmehr stellt sich die Frage, ob der Mietvertrag im Falle der Rückgabe des Mietobjekts ohne Nennung eines zumutbaren Nachmieters einen Rechtsöffnungstitel darstellt (s. unten, E. 3).
1.2.1 Gemäss den Ausführungen der Beschwerdeführerin stellt diese Frage eine Rechtsfrage von grundsätzlicher Bedeutung dar. Es komme in der Praxis häufig vor, dass Mieter das Mietobjekt ausserterminlich kündigten. Diese Frage sei insbesondere im Schuldbetreibungs- und Konkursrecht von erheblicher praktischer Bedeutung, da die Auslegung von <ref-law> durch das Bezirksgericht zu zahlreichen Prozessen führte.
1.2.2 Die Beschwerdegegnerin wendet in ihrer Vernehmlassung dagegen ein, es bestehe kein Anlass, die Beschwerde zu behandeln, da es aller Voraussicht nach gleichartige Sachverhalte geben werde, bei denen die Streitwertgrenze erreicht werde.
1.2.3 Die Frage, ob im Falle der vorzeitigen Rückgabe des Mietobjekts der Mietvertrag ohne Nennung eines zumutbaren Nachmieters einen Rechtsöffnungstitel darstellt oder nicht, hat das Bundesgericht bislang nicht entschieden; sie ist somit neu. Betreffend die Qualifikation des Mietvertrags als Rechtsöffnungstitel bei vorzeitiger Rückgabe des Mietobjekts bestehen unterschiedliche kantonale Praxen (wie die Vorinstanzen bereits der Entscheid des Bezirksgerichts Zürich vom 10. Juni 2003, in: mp 2004, S. 31 f.; abweichend der Entscheid des Präsidenten der III. Zivilkammer des Kantonsgerichts St. Gallen vom 4. Juli 2007, VZ.2007.13, E. III.2a; Urteil des Kantonsgerichtsausschusses Graubünden vom 18. Mai 1993, in: PKG 1993, S. 76 f.; vgl. auch Polivka, Kommentar zum Urteil 4C.36/2005 vom 24. Juni 2005, in: MRA 2005, Rz. 3.1.4 S. 219).
Grundsätzlich besteht ein allgemeines Interesse, dass diese sich in der Praxis immer wieder stellende Frage vom Bundesgericht mit freier Kognition geklärt und damit im Interesse der Rechtssicherheit eine einheitliche Anwendung und Auslegung des Bundesrechts herbeigeführt wird (vgl. dazu <ref-ruling> E. 2.4 S. 649), zumal die Wahrscheinlichkeit, dass diese Frage dem Bundesgericht je unterbreitet werden kann, infolge der Streitwertgrenze äusserst gering ist, da der Streitwert vorliegend selbst bei einem vertraglich vereinbarten Mietzins von jährlich Fr. 60'480.-- nicht erreicht wird.
Es ist somit von einer Rechtsfrage von grundsätzlicher Bedeutung auszugehen. Demgemäss erweist sich die Beschwerde in Zivilsachen als zulässig und ist auf sie einzutreten.
2. Das Obergericht erwog, dass sich die erste Instanz auf eine Lehrmeinung gestützt habe - es wird auf Higi, Zürcher Kommentar, N. 71 zu <ref-law>, Bezug genommen -, wonach der Mieter, welcher die Mietsache dem Vermieter gemäss <ref-law> zurückgegeben hat, ohne einen tauglichen Ersatzmieter zu stellen, in Annahmeverzug gerate, mit der Rechtswirkung, dass kein Mietverhältnis mehr bestehe und eine gesetzliche Ersatzpflicht des Mieters an die Stelle der vertraglichen Erfüllungspflicht trete. Diese Auffassung stimme insofern mit derjenigen der Beschwerdeführerin überein, als auch diese davon ausgehe, dass die Beschwerdegegnerin für ausstehende Mietzinsleistungen bis zum Ablauf der befristeten Mietzeit hafte. Das Bezirksgericht habe vorfrageweise geprüft, ob die in Betreibung gesetzte Forderung als vertragliche Leistungspflicht oder gesetzliche Ersatzpflicht zu qualifizieren sei, sich dabei auf die erwähnte Lehrmeinung gestützt und aufgrund der Annahme, dass ab dem 1. Dezember 2006 kein Mietverhältnis mehr bestanden habe, dem Mietvertrag ab diesem Zeitpunkt die Qualität eines Rechtsöffnungstitels nach <ref-law> abgesprochen. Es handle sich dabei nicht um eine Verletzung klaren materiellen Rechts, wie sie für die Nichtigkeitsbeschwerde nach <ref-law> ZH erforderlich sei, da die Auslegung von <ref-law> durch die Vorinstanz nicht als klar unrichtig, sondern als nachvollziehbar begründet zu betrachten sei. Sie stütze sich auf einen für das Mietrecht bedeutenden Kommentar des Obligationenrechts. Ausserdem ergebe sich aus dem Umstand, dass in dieser Frage unterschiedliche Lehrmeinungen bestünden, dass nicht von klarem materiellen Recht gesprochen werden könne. Ferner resultiere aus der Lehrmeinung von Stücheli (Die Rechtsöffnung, Diss. Zürich 2000, S. 363), dass nach Beendigung des Mietverhältnisses für Schadenersatzanspruch keine Rechtsöffnung mehr erteilt werden könne, selbst wenn dieser dem bisherigen Mietzins entspreche. Die Beschwerdeführerin habe nicht dargelegt, weshalb der von der Beschwerdegegnerin unterzeichneten Verpflichtung zur Mietzinszahlung entgegen dieser vollstreckungsrechtlichen Lehrmeinung auch für die Zeit nach der Rückgabe des Mietobjekts zwingend die Qualität eines Rechtsöffnungstitels zuerkannt werden müsse.
3. Wie die Beschwerdeführerin zutreffend ausführt, bildet der Mietvertrag auch bei vorzeitiger Rückgabe der Mietsache Grundlage für die Leistungspflichten des Mieters und anerkennt der Mieter mit dessen Unterzeichnung seine entsprechende Verpflichtung.
Entgegen den vorinstanzlichen Ausführungen vertritt Higi nicht die Auffassung, dass der Mietvertrag im Falle von <ref-law> dahinfalle. Vielmehr ergibt sich seiner Ansicht nach aus <ref-law> nur dann ein besonderer Beendigungsgrund des Mietverhältnisses, wenn die entsprechenden Voraussetzungen - Rückgabe der Mietsache und Stellung eines zumutbaren Nachmieters - erfüllt sind, ansonsten das Mietverhältnis ordentlicherweise ende (Higi, Zürcher Kommentar, N. 5 zu <ref-law>). Daraus folgt auch, dass Higi nicht - wie das Obergericht ausführt - von einer gesetzlichen, sondern von einer vertraglichen Ersatzpflicht auszugehen scheint (Higi, a.a.O., N. 71 zu <ref-law>; vgl. auch Huber, Die vorzeitige Rückgabe der Mietwohnung, Diss. St. Gallen 2000, S. 128, mit Hinweisen). Unbehelflich sind ebenfalls die weiteren Verweise in der Verfügung des Bezirksgerichts auf BGE 63 II 368 E. 3 S. 372 f. sowie auf Higi, Zürcher Kommentar, N. 58 und 71 zu <ref-law>. In den zitierten Stellen geht es nicht um den Fall der vorzeitigen Rückgabe des Mietobjekts, sondern um die Frage der Mietzinsforderung nach Vertragsablauf bei verspäteter Rückgabe des Mietobjekts. Im Übrigen äussert sich Higi nicht zur Frage, ob der Mietvertrag in den Fällen von <ref-law> als Rechtsöffnungstitel zu qualifizieren ist.
Ob der Anspruch nach <ref-law> als Erfüllungsanspruch oder als Ersatzpflicht zu qualifizieren ist, kann vorliegend offenbleiben. Selbst wenn der Anspruch des Vermieters als Ersatzanspruch betrachtet würde, liesse sich daraus für die Frage der Qualifikation des Mietvertrags als Rechtsöffnungstitel nichts ableiten: Mit der Unterzeichnung des Mietvertrags anerkennt der Mieter die Pflicht zur Mietzinszahlung nicht nur für die Dauer des Besitzes der Mietsache. Vielmehr bezieht sich die Anerkennung auf die gesamte Vertragsdauer. Daran ändert auch die Regelung in <ref-law> nichts; die entsprechenden Umstände, welche zu einer Reduktion der Leistungspflicht führen, sind gegebenenfalls vom Mieter als Einwendungen im Rechtsöffnungsverfahren (<ref-law>) geltend zu machen.
Wie die Beschwerdeführerin ferner zutreffend ausführt, hält auch der vorinstanzliche Hinweis auf die Auffassung von Stücheli nicht Stich: Dieser führt an anderer Stelle aus, der Mieter könne die vorzeitige Entlassung aus seiner Leistungspflicht im Rechtsöffnungsverfahren einredeweise nur geltend machen, wenn er glaubhaft mache, dass er das Mietobjekt zurückgegeben sowie einen zumutbaren Nachmieter gestellt habe (Stücheli, a.a.O., S. 368). Gelingt dies dem Mieter nicht, so ist auch nach Auffassung von Stücheli die provisorische Rechtsöffnung für die bis zum nächstmöglichen ordentlichen Kündigungstermin geschuldeten Mietzinsen zu gewähren (Stücheli, a.a.O., S. 368). Die vom Obergericht zitierte Stelle bezieht sich auf den Fall, dass der Mietvertrag beendigt ist, was im Falle der blossen vorzeitigen Rückgabe der Mietsache gerade nicht zutrifft.
Insgesamt ergibt sich somit, dass ein Mietvertrag im Falle der Rückgabe des Mietobjekts ohne Nennung eines zumutbaren Nachmieters seine Eigenschaft als provisorischer Rechtsöffnungstitel nicht verliert und die Vorinstanzen insofern Bundesrecht verletzt haben.
4. Die Beschwerdegegnerin macht in der Vernehmlassung geltend, sie habe vor Obergericht und Bezirksgericht vorgebracht, dass sie den Mietvertrag mit Schreiben vom 6. Oktober 2006 - somit vor Rückgabe des Mietobjekts per Ende November 2006 - wegen Grundlagenirrtums angefochten bzw. fristlos gekündigt habe. Daher bestehe für den Zeitraum bis Ende November 2006 höchstens eine Ersatzpflicht wegen verspäteter Rückgabe des Mietobjekts und jedenfalls für die Zeit nach November 2006 kein Rechtsöffnungstitel mehr. Im Übrigen sei der Beschwerdeführerin auch nach der Basler Rechtsöffnungspraxis keine Rechtsöffnung zu erteilen, da die vertragsgemässe Erfüllung bestritten werde.
Das Obergericht hat dazu keine Feststellungen getroffen; das Bezirksgericht hat die Frage betreffend diese Einwendungen der Beschwerdegegnerin offen gelassen. Die Vorinstanzen hatten aufgrund ihrer Lösung auch keine Veranlassung, sich zum Alternativstandpunkt der Beschwerdegegnerin zu äussern. Da sich die vorinstanzliche Begründung indes als bundesrechtswidrig erweist, ist die Sache zur Ergänzung des Sachverhalts und zur neuen Beurteilung an das Bezirksgericht zurückzuweisen, zumal die betreffenden Sachverhaltselemente und Argumente vor beiden Vorinstanzen vorgebracht wurden.
Dem Ausgang dieses Verfahrens entsprechend sind die Gerichtskosten der Beschwerdegegnerin aufzuerlegen und hat diese die Beschwerdeführerin für das bundesgerichtliche Verfahren zu entschädigen (Art. 66 Abs. 1 und Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, und es werden die Urteile des Bezirksgerichts Zürich vom 5. Februar 2007 und des Obergerichts des Kantons Zürich vom 30. März 2007 aufgehoben. Die Sache wird zu neuer Beurteilung im Sinne der Erwägungen an das Bezirksgericht Zürich, im Kostenpunkt vor seiner Instanz an das Obergericht zurückgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Bezirksgericht Zürich und dem Obergericht des Kantons Zürich, III. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 5. Februar 2008
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Raselli Rapp