The problem was actually that the service executable was encrypted with EFS; the error code (access denied) threw me off.
The service was being output to a folder that was inadvertently encrypted, so when I copied the service out to the install location, it remained encrypted. Once I unchecked the 'Encrypt contents to secure data' check box in the file's properties, the service correctly started for all users.
This explains why the service would only start as the current user, and not any of the system users, including the privileged 'Local System' account.