I would recommend asking your host to change your server/IP

I contacted them again and they don't want to move me to a different server. They are telling me to contact all those ISPs myself to get the banned IP removed. No way. That's really weird.

I need to move to a different provider and I think it would be a good idea not to host in Germany anymore or at least find a more professional hoster.