Елена, насколько я знаю, платить вам придется. Переезд *- не является причиной для au?erordentliche kundigung, которое требуется в вашем случае.
Вы заключили договор, по определенным условиям AGB, которые предпологают перенос вашего подключения на новое место и минимальный срок договора 24 месяца.

Можно с ними договориться, но при этом проявить готовность к компромиссам. Насколько я знаю, провайдер сейчас отказывается от полного срока договора за определенную плату