The service is not deleted on some machine. A reboot fixes it.
But I was not able to reproduce the failure case and reboot was never needed for me. Maybe the earlier fixes actually solved the problem? Marking it as DoNotMerge until we know that we absolutely need this.