Вы им ещё и доплатить должны, что они это покрытие переняли и вам не надо его сдирать и утилизировать.

Вот не переняли бы они это покрытие, и что бы вы с ним делали? Радуйтесь, что избавили вас от хлопот.

Я, пожалуй, соглашусь с вами. Ибо:

Darf der Mieter seinen Boden mitnehmen?

---

Wurden die Räume ohne Bodenbeläge vermietet, darf der Mieter sie auf eigene Kosten selbst gestalten. Wird das Mietverhältnis beendet, muss der Mieter den ursprünglichen Zustand wiederherstellen. Das bedeutet: Bodenbeläge müssen fachgerecht entfernt und entsorgt werden.

Hat der Vermieter Interesse, die Bodenbeläge zu behalten, so muss er sie gegen eine angemessene Entschädigung vom Mieter ablösen. Die Höhe der Ablöse ist abhängig von der abgelaufenen Nutzungsdauer bei Beendigung des Mietverhältnisses.

Ссылка

Я очень сомневаюсь, что ТС сможет законным способом получить свои деньги, ибо это должно было быть зафиксировано в новом договоре (что представляется мне невозможным, поскольку Vermieter не имеет к этому отношения, он сдавал квартиру изначально без пола на балконе), либо в Vereinbarung между старым и новым квартиросъёмщиком, что, судя по всему, тоже не было правильно оформлено (ТС пишет про какую-то бумажку).

Создаётся впечатление, что новый квартиросъёмщик прекрасно понимает, что может не платить, поэтому и не платит. ИМХО.