I've been getting this message a lot lately:
I'm building a few Windows VMs. The fix is to leave the domain and then rejoin it. It's a bit labor intensive though... is there any way to do this via script and not have to reboot in the middle? Doing it the manual way takes about 3-5 mins.
No, you cannot avoid the reboot. You can script the joining and disjoining of a domain, but you're solving the wrong problem.
The proper approach is not to clone domain-joined VMs in the first place. Create a template of a VM that is in a workgroup, rather than a domain, then rename and domain-join it once it's finished cloning/deploying from a template.
And, as noted by Big Chris in the comments below, don't forget to sysprep, provided you want things like Windows Update and SCCM to work properly.