The problem looks like it's related to the absence of the Post-Windows NT 4.0 Service Pack 6a Security Rollup Package (see KB article 299444) from affected machines. Over 20K have it, and I'm having no problems running the command on them, but around 10K don't and they're the ones with the issue.

Thank you all for helping me work through this!