Susanne 
Wir haben ähnliche Probleme, Mieter zahlt zwar Miete, aber keine NK-Nachzahlung.
Da diese Schulden keinen Grund zur fristlosen nach BGB ergeben, gibt es zur Kündigung folgende Möglichkeit:
Mieter erhöhen nach Mietspiegel/Vergleichswohnung bis zur Kappungsgrenze. Wird die Erhöhung nicht gezahlt, kann man eine fristlose Kündigung aussprechen, wenn sich die Differenz auf 2 MM summiert hat.
Damit aber Deine bisherigen Forderungen aus NK nicht verjähren, musst Du folgendes tun:
Erst einen Mahnbescheid beantragen, der wird zugestellt an den Mieter. Er hat dann 2 Wochen Zeit, dem Mahnbescheid zu widersprechen. Nach Ablauf der 2 Wochen kannst Du (nach Zahlung der durch das Mahngericht angeforderten Gerichtskosten) den Vollstreckungsbescheid beantragen. Gegen diesen kann der Mieter wiederum Einspuch ebenfalls mit einer Frist von 2 Wochen einlegen, der dann gleichzeitig nachträglich als Widerspruch gegen den Mahnbescheid gilt.
Sollte kein Einspruch eingelegt werden, bekommst Du einen Zwangsvollstreckungsbescheid. Mit diesem kannst Du einen Gerichtsvollzieher mit der Einziehung Deiner Forderungen beauftragen oder ihn mit Abnahme der eidesstattlichen Versicherung beauftragen oder ne Kontenpfändung vornehmen bzw. Lohn-Gehaltspfändung usw.
meglan
für die detailierte auskunft.
bin eigentlich froh wenn er aus der wohnung ist.
da er arbeitslos ist, scheint es mir eh aussichtslos die NK zu holen.
was noch interessant ist: ich meine er hätte einmal erwähnt, er hätte eine privatinsolvenz am laufen.
das werde ich wohl mal durch einen rechtsanwalt prüfen lassen.
wie wollt ihr denn jetzt euer problem lösen? den tip mit der mieterhöhung?
Dionysos 
Nach den Ausführungen von Susanne nur zwei Ergänzungen: nach dem BGB beträgt die Verjährungsfrist drei Jahre, wenn die Forderung nicht tituliert ist, daher würde ich sofort das gerichtliche Mahnverfahren (von Susanne beschrieben) einleiten. Zumindest für die älteste Forderung.
Die Sache mit der Privatinsolvenz ist m.E. ein Trick, denn ansonsten hättest du von dem Insolvenzverwalter als Vertragspartner eine Information und eine Anmeldung von Forderungen erhalten müssen.
Sollte das Insolvenzverfahren VOR dem Einzug bei dir eingeleitet worden sein, bekommst du spätestens beim gerichtlichen Mahnverfahren (ab der Stelle mit dem Gerichtsvollzieher) Klarheit. Und dann ist es eine schönes Gefühl die Restentschuldung nach der Wohlverhaltensphase verhindert zu haben *g*.
LG
Dionysos
Heute ist die "Gute, alte Zeit" von morgen.