All my other devices can connect to nc.local as well as other names with .local, but the phone with GrapheneOS.
While running nslookup (on my computer), I did find out that the IPv6 is used as default and fails to resolve, might be due to how I setup my PiHole. But it works when I manually enter the IPv4 address of PiHole when running nslookup.
I'll try and fix PiHole's network configuration to make it work with IPv6 when I have more time and come back with results.
But I still find it weird that it used to work on my GrapheneOS device but stopped working after a month or so. The DNS servers on the GrapheneOS network settings shows both IPv4 and IPv6 addresses of PiHole, so technically it should resolve by reaching the IPv4 server even it didn't manage to reach the IPv6 DNS server?