I am running Arch Linux with the 4.19.12-arch-1-ARCH kernel, and samba --version yields 4.9.4.
The problem is this:
Whenever I reboot my machine, I cannot resolve WINS addresses (wbinfo -N <WINS name> returns "Could not lookup WINS by name <WINS name>"), until after I restart winbind (systemctl restart winbind), and then re-query the NAS I'm trying to reach (wbinfo -N <WINS name>). For this same reason, my fstab which contains mount points for my NAS doesn't mount everything...after restarting winbind, I can run "mount -a" and the NAS mounts work.
So, it seems there's some sort of order dependency in winbind. It's almost as if winbind starts too early, the fstab tries to mount (and fails), and winbind caches the unresolved address...restarting winbind recreates the host query cache. It seems for failed queries, it should re-attempt to resolve the host via the network, and not the cache. I have been having this issue for a few months now. I have another Ubuntu machine that does not exhibit this symptom, but I haven't updated samba on that one in probably 6 months.