Wir haben bisher zur Miete gewohnt und haben einen Garten (der zum Mietobjekt dazugehört) angelegt. Nun haben wir gebaut und der Vermieter verlangt von uns, dass wir alle Pflanzen wieder ausgraben. Wir haben zwar Zeit und Geld investiert, wollen die Pflanzen aber nicht mitnehmen.

Ja, das darf er von Euch verlangen, da der Mietvertrag ja nur die Nutzung der vorhandenen Räume/Flächen gestattet. Werden Änderungen vorgenommen, muss, sofern es der Vermieter verlangt der UR-Zustand wieder hergestellt werden. Natürlich ist ein schöner Baum oder auch eine Hecke eine Bereicherung, aber das Mähen des Rasens wird erschwert, der Rasen kann kahle Stellen durch den Schattenwurf des Baumes bekommen und das Laub verursacht zusätzliche Arbeit, die Geld kosten kann, oder einen interessierten Nachmieter davon abhalten kann diese Wohnung zu beziehen - wirkt sich also Geschäftsschädigend aus. Wenn die Bäume nicht allzulange schon im Garten sind, ist der Herbst der Ideale Zeitpunkt um diese wieder auszugraben und in den neuen Garten zu setzen, sofern dieser schon fertig ist. Ist dies nicht der Fall, raus damit und wegschmeißen. Viel Erfolg.
Ich könnte mir vorstellen, dass er sich um das Wachstum der Bäume sorgt. Wenn die erst groß sind, darf man sie unter Umständen nicht mehr so einfach fällen, außerdem ist Fällen lassen teuer. Normalerweise ist es doch so, dass Mietobjekte in dem Zustand zurückgegeben werden sollten, in dem man sie übernommen hat (Ich bin kein Fachmann diesbezüglich) und das gilt sicherlich ebenso für Gärten. Lauben/Gartenhäuschen beispielsweise muss man ja auch wieder abbauen. Wenn ihr die Pflanzen nicht mitnehmen wollt, werdet ihr sie wohl roden und entsorgen müssen. Oder vielleicht gibt es bei euch auch eine Pflanzenbörse, in unserer Stadt ist sowas im Herbst manchmal.
Eigentlich ist er ein Depp, denn solange ihr keine Abstandszahlung verlangt und nichts außergewöhnlich-unvermeitbares angelegt habt, sollte er sich doch über den Garten freuen.
Aber wir wissen natürlich nicht, was für einen Wald ihr aus der Blumenwiese gemacht habt :-)