I work for a small part of a large organization that has been on the internet since dinosaur days (pre-CIDR). I'm confident our DNS is properly configured, but a tiny fraction (<1%) of our remote clients have chronic problems (either continuous or sporadic) resolving our host names (e.g. anything at *.foobar.org). EDIT: these are long-standing A records, not recent changes.
I ask them to switch to Google DNS, which usually solves the problem. However, some clients are skeptical, since they can reach our competitors (e.g. bizzbuzz.org or qux.com) without any trouble. Honestly, I wonder the same thing. Why does it happen?
What are some troubleshooting steps we can do (other than flying to Albuquerque or wherever to test their cable company's local loop) to definitively determine why their DNS fails and how to fix it?