Da ich eine ähnlich geartete Problematik (DCHP nach Neustart schlägt fehl) hatte, hier meine aktuelle Hypothese bzgl. einer möglichen Ursache:
Ich vermute die neu eingeführte Firewall (auf netcup Seite) als Ursache.
Wenn ich die FW für den Server komplett auf den Standardeinstellungen belasse, dann gibt es keine Probleme.
Füge ich jedoch beispielsweise eine eigene Regel hinzu (z.B. "allow 22/tcp"), ändern sich automatisch die "Implizieten Regeln" von "INCOMING ACCEPT ANY" hin zu "INCOMING DROP ANY".
Setze ich die Firewall zurück auf die Default Settings und führe einen Reboot durch, dann funktioniert DHCP problemlos.