This issue seems to be known on Windows XP. This Microsoft article explains how to resolve it: You need to restart task scheduler service on the affected machines. After 15 minutes test deploying again.
As a test, I tried the deployment from the native deployment tool in the software that I was attempting to install and it worked. In the grand scheme, these are a relatively small percentage of our clients, so I probably won't pursue the solution here. Thanks again for the quick suggestion.
This issue seems to be known on Windows XP. This Microsoft article explains how to resolve it: You need to restart task scheduler service on the affected machines. After 15 minutes test deploying again.