Your analysis is correct, the deployment tend to fail if the scheduler service is not running on the client machine. Since you are unable to re-install the scheduler from the Protect console, my suggestion would be to manually uninstall then re-install the scheduler on this client using this guide: How To: Uninstall & Reinstall The Shavlik (ST) Remote Scheduler Service On A Single Machine
1 of 1 people found this helpful
Under the tools\options menu is a Scheduler tab.
You might try using selecting Microsoft Scheduler instead of the Shavlik scheduler. Then try to deploy to the machine that is not currently working.
This a an overall setting so it will start using the MS Scheduler for all deploys.