The solution was to correct the port values for the AD service records of our DNS.
In our bind 9 config, we have 11 special Active Directory "site" files:
_msdcs.your.domain.here.hosts
_tcp.e6b6bf1d-0a16-4441-a066-32a59b46b65d.domains._msdcs.your.domain.here.hosts
_tcp.dc._msdcs.your.domain.here.hosts
_tcp.Default-First-Site-Name._sites.dc._msdcs.your.domain.here.hosts
_tcp.Default-First-Site-Name._sites.gc._msdcs.your.domain.here.hosts
_tcp.Default-First-Site-Name._sites.your.domain.here.hosts
_tcp.gc._msdcs.your.domain.here.hosts
_tcp.your.domain.here.hosts
_tcp.pdc._msdcs.your.domain.here.hosts
_udp.your.domain.here.hosts
8 of these files have LDAP SRV records, and in our case, all of them had the wrong LDAP port. I replaced all the 289 values with 389, and restarted the name server. Now the result from dig +short -t srv _ldap._tcp.your.domain.here
is
0 0 389 melbourne.your.domain.here.
And Macs are finally able to bind. I cannot explain why only the Macs are sensitive to the mis-configured DNS.
Our particular mis-configuration was a specific fault, but it is clear that DNS can be a problem for binding Macs to AD. So explore that when you are troubleshooting the dreaded Node name wasn't found (2000)
error.