Yes, we've managed to solve this, but it was more of sum of things that weren't working properly.
Our firewall was blocking the DNS port, so other DNS servers couldn't read the DNS changes. Also we've done some changes in the DNS config to let the AXFR records work.
When I'm tring to lookup NS on subdomain.example.com, I'm getting "no records found". I've got that same error when looking up existing subdomains that are working.
When creating the subdomain in Plesk, it automatically makes 2 NS records: ns1.subdomain.example.com and ns2.subdomain.example.com...
Yes, we tried adding the A-record to the main domain name, but unfortunately that doesn't work.
Somehow it seems like the A-record doesn't get "through" or "published" in Plesk, because on MXtoolbox he still doesn't find any A-records.
Since a few months we're having trouble creating subdomains in our plesk environment.
We have over 100 subdomains and domains, but since a few months, when we create a subdomain and the required A record in the main domain, we keep getting "DNS_PROBE_FINISHED_NXDOMAIN" in Chrome, stating that...