This error was too generic to be useful and there was no pattern to this bizarre behaviour.
I eventually found the problem. ISATAP had not been removed from the Global Query Blocklist on one of the DNS servers.
Note that this is not an automatic process. It has to be done manually on all DNS servers. I removed ISATAP and restarted the DNS Server service.