I see you have edited your answer while I was replying:
This would indicate that your issue is with the nameservers that the OS on the device running Pi-hole is using.
Obviously, overwriting resolv.conf with a public nameserver fixes your issue, but that fix is only temporary. Your device OS will update nameservers as received from your network's router.
That may suggest that your router is advertising its own IPv6 as local DNS server, or perhaps a non-existing one.
As your debug log indicates your router to be a FritzBox, you may try to disable your router's propagation of IPv6 DNS servers , see e.g. Unresolved ipv6 adress in my top list - #4 by Bucking_Horn.