We run into this fairly often. DENIC does not allow you to use a nameserver if asking it for NS records returns a response that does not include that nameserver. This is intended to prevent users from shooting themselves in the foot with an invalid configuration.
In our case, we return NS records for either the last known active registration (even if it has since been deleted) or the earliest pending registration. These NS records are eventually purged if there is no active registration, but that process takes some time (~2 weeks).
Because of this, we can, on request, purge those records early. This does also wipe out your pending registration, but if you recreate it we’ll return your nameservers and you’ll be able to configure them with DENIC.