Thanks to the hint here I solved this myself:
I had an correct IPv6 AAAA DNS entry. Anyway for the working subdomains there was no such entry.
After removing the AAAA entry now the certificate is issued as before.
So DNS seems to be a good place to look for in similar situations.