Also wenn die Wohnungssuche nach Eingang der Kündigung einsetzte, sehe ich kein Problem. Das nennt sich Anscheinsbeweis, das heißt es ist allem Anschein nach so, dass der Mieter anlässlich der Kündigung anfing, eine Wohnung zu suchen, und sonst damit nicht angefangen hätte. Anders wäre es, wenn der Mieter vielleicht vorher in einer anderen Stadt eine Arbeitsstelle gefunden hätte und sowieso wegziehen musste. Dann wäre die potenziell irreguläre Eigenbedarfskündigung nicht ursächlich für den Umzug und Schadensersatzansprüche wären schwierig.
Wenn der Mieter also glaubhaft darlegen kann, dass er erst nach Eingang der Kündigung angefangen hat, eine neue Wohnung zu suchen, beispielsweise durch das Anmeldedatum bei einem Online-Portal, dann wird er gute Karten haben. Der Vermieter müsste dann beweisen, dass er trotzdem rechtmäßig gehandelt hat - in seltenen Fällen kann es sein, dass eine solche Eigenbedarfskündigung rechtmäßig war, zum Beispiel, wenn die Wohnung für einen Verwandten vorgesehen war, der später aus nicht vorhersehbaren Gründen nicht einziehen konnte.