1. Ich habe diese mündliche Vereinbarung "er sucht, ich suche" nie als offizielle Kündigung angesehen, sondern eher als so ein "Laß uns mal gucken, wir kriegen das schon hin, auch ohne Druck". Und selbst wenn es eine Kündigung war - bräuchte ich die nicht schriftlich?
Richtig. Mündliche Kündigungen sind so viel wert, wie ein leeres Blatt Papier.
2. Nehmen wir an, die Kündigung war rechtens:
Das war sie aber nicht, also sollte man auch nicht darüber reden.
3. Stutzig gemacht hat mich allerdings folgende Klausel aus meinem (damals ziemlich naiv unterschriebenen) Untermietvertrag: "Das Kündigungsrecht des Hauptmieters richtet sich nach den gesetzlichen Vorschriften, wenn der Untermietvertrag auf unbestimmte Zeit geschlossen wurde. Die Frist beträgt somit zwei Wochen."
Dieser Punkt 3 im Vertrag gilt nur für Mietverhältnisse über ein möbliertes Zimmer. Diese unterliegen auch nicht dem strengen Mieterschutz des BGB. Da du dein Zimmer selbst möbliert hast gilt hier § 573a BGB, das heißt deine Kündigungsfrist beträgt 3 + 3 Monate. Also Zeit genug, um was passendes zu finden.
Fahr in Ruhe in Urlaub und kümmere dich danach um eine neue Bleibe.