Turns out it was the fallback configuration for coreDNS that had kicked in and it constantly tried to connect to Cloudflare DNS which is prevented by my firewall.
Disabling the fallback feature fixed this issue. Command for disabling it is: ha dns options --fallback=false
Also a big thank you to the redditor /u/tallr0b which pointed me to this thread Improve Privacy, Stop using hardcoded DNS which gave me the solution.