A. A. und B. (Beschwerdeführer 1) bewohnen eine 4 1/2-Zimmerwohnung an der D.-Strasse 308 in Basel. C. (Beschwerdeführerin 2) ist Mieterin einer 2 1/2-Zimmerwohnung an der D.-Strasse 310 in Basel. Aufgrund einer Sanierung im Jahre 2002 zeigte die X. Gesellschaft (Beschwerdegegnerin), vertreten durch ihre Tochtergesellschaft X. Immobilien AG, am 7. November 2003 Mietzinserhöhungen an, den Beschwerdeführern 1 von Fr. 1'204.- auf Fr. 1'314.-, der Beschwerdeführerin 2 von Fr. 717.- auf Fr. 798.-. Nachdem vor der Schlichtungsstelle keine Einigung erzielt werden konnte, gelangte die Beschwerdegegnerin an das Zivilgericht Basel-Stadt und beantragte, die Mietzinse entsprechend den bekanntgegebenen Erhöhungen festzusetzen. Der Zivilgerichtspräsident hiess beide Klagen am 27. August 2007 gut. Die gegen diese Entscheide ergriffene kantonale Beschwerde wies das Appellationsgericht Basel-Stadt am 30. April 2008 ab.

B. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer im Wesentlichen, es sei festzustellen, dass die Mietzinserhöhungen missbräuchlich seien. Die Beschwerdegegnerin schliesst auf kostenfällige Abweisung der Beschwerde, soweit darauf einzutreten sei.

Das Bundesgericht weist die Beschwerde ab, soweit darauf einzutreten ist.

1. Die Beschwerdeführer sind der Auffassung, die Mietzinserhöhung sei nichtig, da sie nicht auf einem von der zuständigen Behörde genehmigten Formular erfolgt sei. Sowohl der Vertreter der Beschwerdeführer als auch der erstinstanzliche Richter hätten von der zuständigen Behörde die Auskunft erhalten, das verwendete Formular sei nicht genehmigt worden. Indem die kantonalen Instanzen dennoch von einem genehmigten Formular ausgingen, hätten sie sich eine Zuständigkeit angemasst, die ihnen nicht zukomme.

1.1 Die Vorinstanz hielt in tatsächlicher Hinsicht fest, die Tochtergesellschaft der Beschwerdegegnerin, welche diese vertreten hatte, habe ihre Firma geändert, aber noch unter der ursprünglichen Firma die Genehmigung für ein Erhöhungsformular erhalten. Daher sei sie nicht verpflichtet gewesen, nach dem Firmenwechsel eine erneute Genehmigung einzuholen, da es sich um dieselbe Rechtsperson handle, der das Formular bewilligt worden war.

1.2 Nach Art. 269d Abs. 1 OR muss der Vermieter eine Mietzinserhöhung auf einem vom Kanton genehmigten Formular mitteilen und begründen. Die Mietzinserhöhung ist nichtig, wenn der Vermieter sie nicht mit dem vorgeschriebenen Formular mitteilt (Art. 269d Abs. 2 lit. a OR). Das Formular für die Mitteilung von Mietzinserhöhungen muss nach Art. 19 der Verordnung vom 9. Mai 1990 über die Miete und Pacht von Wohn- und Geschäftsräumen (VMWG; SR 221.213.11) den bisherigen Mietzins sowie die bisherige Belastung des Mieters für Nebenkosten, den neuen Mietzins sowie die neue Belastung des Mieters für Nebenkosten, den Zeitpunkt, auf den die Erhöhung in Kraft tritt, und die klare Begründung der Erhöhung enthalten. Werden mehrere Erhöhungsgründe geltend gemacht, so sind diese je in Einzelbeträgen auszuweisen. Dass ein Formular inhaltlich den Anforderungen von Art. 19 VMWG entspricht, genügt nicht. Aus Gründen der Klarheit und einheitlichen Handhabung sowie der Rechtssicherheit ist notwendig, dass das Formular von der zuständigen kantonalen Instanz genehmigt wurde (BGE 121 III 214 E. 3b S. 217).

1.3 Eine Verletzung der Zuständigkeitsvorschriften, wie sie die Beschwerdeführer geltend machen, läge vor, wenn die kantonalen Gerichte das betreffende Formular selbst an Stelle der kantonalrechtlich hierfür vorgesehenen Behörde genehmigt hätten. Kommt demgegenüber der Richter im Rahmen eines Prozesses zum Ergebnis, das für die Erhöhung verwendete Formular sei von der zuständigen Behörde genehmigt worden, stellt er lediglich den im Prozess massgeblichen Sachverhalt fest. Ausserhalb des Prozesses kommt dieser Sachverhaltsfeststellung keine Bedeutung zu. Da der Richter keine Genehmigung des Formulars vornimmt, ist auch keine Verletzung der Zuständigkeitsordnung gegeben. Es stellt sich einzig die Frage, ob die Sachverhaltsfeststellung angesichts der anderslautenden Auskünfte der zuständigen Behörden korrekt erfolgte.

1.4 Auf Beschwerde in Zivilsachen hin kann das Bundesgericht zwar prüfen, ob eine Feststellung in tatsächlicher Hinsicht offensichtlich unrichtig und damit willkürlich ist (Art. 97 Abs. 1 BGG). Der Rechtsuchende hat indessen im Einzelnen darzulegen, weshalb die Auffassung der Vorinstanz offensichtlich unhaltbar und damit willkürlich sein soll (BGE 133 II 249 E. 1.4.3 S. 254 f.; BGE 133 III 462 E. 2.4 S. 466 f.). Die Beschwerdeführer berufen sich auf die von den zuständigen Behörden erteilten Auskünfte und machen geltend, es sei von der urteilenden Instanz nicht nachzuprüfen, ob diese Auskunft richtig oder falsch sei. Zur Begründung einer Willkürrüge müssten die Beschwerdeführer aber darlegen, inwiefern die Annahme, die Auskünfte seien falsch, offensichtlich unhaltbar und damit willkürlich ist. Dazu genügen ihre Ausführungen nicht, so dass der angefochtene Entscheid insoweit nicht zu überprüfen ist.

1.5 Als aktenwidrig rügen die Beschwerdeführer die Feststellung der Vorinstanz, die Beschwerdegegnerin habe für die Mietzinserhöhung das genehmigte Formular verwendet. Nicht nur die grafische Gestaltung sei völlig unterschiedlich, auch die Firmierung sei eigenhändig abgeändert worden. Zudem sei der Hinweis "Formular genehmigt durch die zuständige Amtsstelle" beigefügt worden.

1.5.1 Der Vorinstanz ist nicht entgangen, dass die beiden Formulare nicht identisch sind, wies sie doch ausdrücklich auf die Firmenänderung hin. Die Vorinstanz ging vielmehr davon aus, die abweichende Gestaltung ändere nichts daran, dass es sich um ein genehmigtes Formular handle. Ob diese Annahme zutrifft, ist eine Rechtsfrage, welche das Bundesgericht unter dem Blickwinkel des Bundesrechts (mit Ausnahme der verfassungsmässigen Rechte der Beschwerdeführer) von Amtes wegen prüfen kann (Art. 106 BGG). Soweit keine hinreichend begründeten Sachverhaltsrügen erhoben werden (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG), stützt sich das Bundesgericht dabei grundsätzlich aber auf die im angefochtenen Entscheid enthaltenen tatsächlichen Feststellungen (Art. 105 Abs. 1 BGG).

1.5.2 Soweit sich Abweichungen zwischen dem genehmigten und dem verwendeten Formular nicht bereits aus den tatsächlichen Feststellungen im angefochtenen Entscheid ergeben, müssten die Beschwerdeführer diesbezüglich substantiiert eine Ergänzung des Sachverhalts beantragen und danach ausführen, inwiefern die Annahme, das Formular habe trotz der Änderung als genehmigt zu gelten, Recht verletzt (Art. 42 Abs. 2 BGG). Diesen Anforderungen genügen die Vorbringen der Beschwerdeführer nicht. Ob eine Abänderung dazu führt, dass das geänderte Formular als nicht genehmigt anzusehen ist, kann nämlich nicht ohne Rücksicht auf die vorgenommenen Modifikationen und den mit dem Formularzwang verfolgten Zweck entschieden werden. So unterscheidet sich das verwendete vom genehmigten Formular beispielsweise darin, dass die Adresse der Mietschlichtungsstelle aktualisiert wurde. Es versteht sich von selbst, dass die korrekte Adressangabe vom Gesetz gewollt ist und der Nachvollzug der Adressänderung nicht dazu führt, dass erneut eine Genehmigung eingeholt werden müsste.

1.5.3 Auf die einzelnen Abweichungen braucht indessen nicht näher eingegangen zu werden, denn die Beschwerdegegnerin verweist auf zwei bei den Akten liegende genehmigte Formulare anderer Liegenschaftsverwaltungen, die mit Ausnahme der Geschäftsfirma und deren Logo mit dem von der Beschwerdegegnerin verwendeten Formular identisch sind. Die Beschwerdeführer berufen sich zwar auf ein im Kanton Luzern ergangenes Urteil (LGVE 1993 I Nr. 9 S. 10 ff.), gemäss welchem die Genehmigung privat kreierter Formulare personenbezogen zu erfolgen hat, damit der zuständigen Behörde bei Anfragen eine effiziente Kontrolle, ob ein Formular genehmigt wurde, ermöglicht wird. Diese liesse sich indessen besser erreichen, indem das Formular mit einer Identifikationsnummer versehen wird. Der Umfang des notwendig vorformulierten Formularinhalts wird abschliessend durch Art. 19 VMWG geregelt (HIGI, Zürcher Kommentar, 4. Aufl. 1998, N. 190 zu Art. 269d OR mit Hinweis). Aus Art. 19 Abs. 4 VMWG ergibt sich, dass der Vermieter genehmigte Erhöhungsformulare beziehen können muss, was voraussetzt, dass unpersönliche Formulare zur Verfügung gestellt werden. Unterscheidet sich das verwendete Formular von einem genehmigten nur in der Firma und dem Kennzeichen des unterzeichnenden Unternehmens, betrifft die Abweichung den individuell auszufüllenden und nicht den allgemeingültigen und damit der Formalisierung überhaupt zugänglichen Teil des Formulars. Mit der Bezeichnung der Vermieterschaft oder der für diese handelnden Gesellschaft wird für den Mieter ersichtlich, wer das Formular verwendet. Dass der Mieter die notwendigen Informationen in der vom Kanton genehmigten Form erhält, bleibt garantiert, solange weder inhaltlich noch in der Darstellung weitere Änderungen vorgenommen werden. Damit ist dem Zweck von Art. 269d OR, dem Mieter den Rechtsweg aufzuzeigen und ihm eine möglichst einfache Beurteilung seiner Chancen zu sichern, die angekündigte Mietzinserhöhung anzufechten, Genüge getan und diesbezüglich die vom Gesetz gewollte vorgängige Kontrolle gewährleistet (BGE 121 III 214 E. 3b S. 217 mit Hinweisen). Aufgrund der Aktenlage ist somit erstellt, dass das verwendete Formular einem von der zuständigen Behörde genehmigten entspricht. Gegenüber wem und mit welchem Firmenlogo diese Genehmigung erfolgte, ist nicht massgebend.