Mietvertrag gültig?

Hallo zusammen,
ich bin auf dieses Forum gestoßen, da ich momentan in einer schwierigen Mietsituation stecke. Ich fang am besten mal mit allgemeinen Angaben zur meiner Situation an, um das ganze besser einordnen zu können.

Meine Freundin und ich suchen momentan unsere erste gemeinsame Wohnung. Relativ schnell wurden wir auch fündig.
Die Wohnung befindet sich in einem ehemaligen Einfamilienhaus. Die Vermieter (älteres Rentnerpaar) haben beschlossen die erste Etage zu vermieten. Vorher wohnte da immer Familie drin. Bei der Wohnungsbesichtigung waren wir uns sehr sympathisch und wir haben entschlossen die Wohnung zu nehmen. Der Vertrag wurde uns in zweifacher Ausführung (ohne Unterschrift des Vermieters) vorgelegt. Sofort unterschreiben wollten wir nicht, haben die Verträge also mit nach Hause genommen und dort unterschrieben.

An dem Tag, an dem wir uns zur Vertragsübergabe verabredet haben, hab ich mich interessehalber bei der Telekom informiert, was bzgl. Internetleitung in dem Haus so möglich ist. Dort wurde mir gesagt, dass ich keinen eigenen Tarif beantragen könne, weil im Haus nur eine Telefonleitung liegt und die vom Vermieter belegt ist.

Bei der Vertragsübergabe habe ich diesen Punkt angesprochen und klar gemacht, dass wir schon unsere eigene Telefonleitung haben möchten und uns nicht einen Internetanschluss mit den Vermietern teilen möchten. Darauf wurde eher mit Unverständnis reagiert. Es folgte auch noch ein heißes Gespräch mit dem Sohn, der sich für ein Fachmann hielt und sehr unsympathisch reagierte.

Wir sind dann so verblieben, dass die das mit de Leitung klären und wir uns dann wieder zusammen setzen. Mein Exemplar habe ich wieder mitgenommen, das andere blieb bei den Vermietern (mit meiner Unterschrift). Mündlich hatten wir abgemacht, dass der Vermieter nicht unterschreibt, solange das nicht geklärt ist und im Vertrag festgehalten wird, dass wir eine zweite Leitung bekommen.

Die ganze Sache hatte meine Freundin und mich aber schon soweit beunruhigt, dass wir uns entschieden haben die Wohnung doch nicht zu nehmen. Das Kommunikationsverhalten des Vermieters war einfach nicht wie wir es uns gewünscht haben. Jetzt ist natürlich das Blöde, dass ein Vertragsexemplar mit unserer Unterschrift dem Vermieter vorliegt. Ist der Vertrag damit gültig, oder müssen beide Exemplare auch vom Vermieter unterzeichnet sein?

Gemäß der 3 Monate Kündigungsfrist möchten wir auch direkt morgen die Kündigung vorbeibringen. Damit wäre zum 30.6 (Einzug wäre am 1.7) gekündigt. Im Prinzip wäre das also nicht das Problem, da wir noch vor der ersten Miete gekündigt hätten.
Im Vertrag haben wir aber eine Klausel einbauen lassen, die uns bestätigt, dass das Bad vor dem 1.7 noch renoviert wird. Dabei müssen wir die Kosten der Fliesen übernehmen, Sinatäranlagen und Handwerke bezahlt der Vermieter. Da der Vermieter über unseren kurzfristigen Rückzug natürlich sehr ungehalten ist, könnte er uns jetzt doch rein theoretisch richtig einen reinwürgen, indem er die teuersten Fliesen nimmt, die er finden kann, oder?

Wie man an dieser Geschichte erkennen kann, bin ich in solchen Dingen sehr unerfahren und auch sehr blauäugig an die Sache rangegangen. Ich hoffe, dass ich hier ein paar hilfreiche Tipps bekommen kann, wie ich mit dieser Situation umzugehen habe. Dafür schon mal vielen Dank und

herzliche Grüße
Tobo

P.S.: In einem weiteren Telefongespräch hat der Vermieter mir zugesichert, dass ich "so nicht davon komme". Die Gesprächsbereitschaft des Vermieters, die ganze Sache noch so zu regeln, ist daher eher gering.

Erstmal vielen Dank für die vielen und schnellen Antworten. Das Kündigungsschreiben habe ich schon aufgesetzt. Morgen früh werden meine Freundin und ich direkt morgens dahin und die Kündigung vorbeibringen. Zur not in den Briefkasten schmeißen, falls niemand aufmacht.
Ich hab auch nochmal genau im Vertrag nachgeschaut. Der Mietvertrag ist ein Standardformular von "Haus & Grund". Ich weiß nicht ob jemand damit Erfahrung hat? Darin steht nichts spezielles zur Kündigungsfrist.

Zur Renovierung des Bads wurde handschriftlich folgendes festgehalten, dass die Boden- und Wandfliesen in Absprache mit den Mietern ausgesucht werden. Von daher kann er sich wohl keine goldenen Fliesen auf unsere Kosten anschaffen. Aber generell ist die Klausel schon wirksam, auch wenn wir gar nicht einziehen und er noch nicht mit der Renovierung oder Materialbeschaffung begonnen hat?

Im Kündigungsschreiben spreche ich beide Vermieter (Eheleute) an und habe als Absender auch meine Freundin und mich eingetragen. Unterschrieben wird das Ganze natürlich auch von uns beiden. Ich habe auch gelesen, dass die Kündigung unbedingt allen Vermietern ausgesprochen werden muss. Reicht es denn trotzdem, wenn wir das Schreiben einem von beiden in die Hand drücken?