Susanne 
Du hast recht. Bitte die Mieterhöhung von einem Fachanwalt prüfen lassen, sie ist m.E. nichtig.
Gründe:
"Wegen steigender Kosten" ist kein möglicher Grund nach BGB.
Die Miete muss mind. 1 Jahr Mietdauer gleich bleiben. Mit korrekter Ankündigungsfrist der Mieterhöhung sind es insgesamt sogar 15 Monate. (Mieterhöhung nach 12 Monaten + korrekte Ankündigungsfrist)
bitterlemon
für deinen schnellen Kommentar. Ich werd mir mal die Paragraphen raussuchen und den Vermieter damit konfrontieren. Mal sehen,was er dazu sagt. Danke nochmal.
Susanne
Auf eine nichtige Mieterhöhung muss man nicht reagieren, daher würde ich die Prüfung durch einen Fachanwalt vorschlagen und dann, wenn Du diesbezüglich Rechtssicherheit hast, den VM einfach auflaufen lassen und gar nichts machen.
Dionysos 
Hallo Bitterlemon,
es ist durchaus möglich, schon vor der 12-Monatsgrenze die Miete zu erhöhen.
Die eine Möglichkeit ist, dass die Wohnung öffentlich gefördert ist (also zum Bezug ein Wohnberechtigungsschein erforderlich ist). Dann kann auf Grund gestiegener Aufwendungen akut zum 01.01.08 die Miete erhöht werden. Die Mieterhöhung beträgt bei den Kostenarten (NICHT insgesamt) ca. 6%. Dies betrifft auch die Mieter, die noch nicht solange dort wohnen.
Eine andere Möglichkeit wäre die Erhöhung nach §560 BGB im frei finanzierten Bereich, nämlich dann, wenn eine Betriebskostenpauschale vereinbart worden ist. Wenn der Vermieter absehen kann, dass die Pauschalen die Kosten nicht decken, kann er diese einseitig mit Erklärung in Textform erhöhen.
Leider lässt sich aus der Begründung "wegen steigender Kosten" nicht viel ableiten.
Sollte der Erhöhungsgrund §558 BGB sein, treffen deine Angaben zu (20% in drei Jahren, 12 Monate unverändert, usw.) und die Miete durfte nicht erhöht werden.
Ich hoffe, ich konnte dir ein wenig helfen.
LG
Dionysos
Heute ist die "Gute, alte Zeit" von morgen.