While it is difficult to diagnose specifically what is going on without seeing logs and reproducing the issue, I have the following general suggestions.
1) Ensure Windows Automatic Updates is disabled when patching with Shavlik as the two programs will compete for the same processes slowing down the deployments and creating unexpected behavior. This is discussed here Best Practice: Windows Automatic Updates .
2) Since as you mentioned, some patches need a reboot before-hand, you can configure the machines to reboot before the deployment in the Pre-deploy reboot options of the deployment template.
3) Antivirus can hamper deployments as well because it can quarantine some of our processes. Make sure that the processes and files mentioned under the Agentless Deployments section of AntiVirus Exclusions For Patch Deployments are white listed in your Antivirus.
4) Sometimes there are corrupt system files that can cause deployment issues and I always highly recommend running sfc /scannow in an elevated command prompt on the affected system. You usually will not see any feedback on problems, but it helps many times.
We are going to do a test this evening. We have disabled windows update and will attempt the pre-patch reboot On several servers having 50+ patches Outstanding. Then repart back how that goes.
A follow on question. We had a server missing 165 updates, we set Shavlik to scan and patch the server. One of the patches required a reboot so the server rebooted. Once the server rebooted more patches were waiting to complete and that process did not complete till a user with admin rights logged into the server. At which point the patching process completed. We are using agentless patching. How do we get the patch process to complete without a user login into the server? Would having the Shavlik Agent installed have completed the patching process?
The 4 machines we tested on did not do the pre scan reboot, the Patch Progress in the deployment tracker for one of the machines shows Patch Progress Executed 0 of 73. I logged into the machine and it did not reboot according to the event logs and no sign that patches attempted.
Did a Scan, Patch and with Reboot. Same results Patch Progress Executed just hung at 0 of 73.
So I did a manual reboot on the target machine and did Scan, Patch and with Reboot, now the deployment tracker is moving forward.