Thanks; this new server (Plesk 12.5.30#45 CentOS 6.8) was rebooted and I just tried to delete some subdomains by CP, which was successful, so have not tested the repair db suggestion.
In my case, for subdomain x.app.domain.nl, this returns the following:
[root@app log]# plesk bin subdomain -r x.app.domain.nl
Unable to find domain with name 'x.app.domain.nl'
Same goes for "plesk bin subdomain -r x -domain app.domain.nl" and "plesk bin subdomain -r x.app -domain domain.nl"...