I have endless DNS problems with Tailscale. So I am guessing it’s a hard problem.

It's like the haiku says:

It’s not DNS

There’s no way it’s DNS

It was DNS