Thanks for helpfull artical.
I think that a lot of people, particularly IT people, like to stop agents like this as soon as they can...they all perceive a performance hit from anything, whether real or imagined. Being able to prevent and enforce the policy is a godsend.
I find it strange no one else discusses this issue but I had exactly the problem you describe where the service will not start.
Secondly, MAKE SURE YOU ADD 'AUTHENTICATED USERS' to have only READ rights to this GPO, other wise, the agents will stop reporting and NEVER start.
For clarification though, this should read: "ADD 'AUTHENTICATED USERS' to have only READ rights to this SERVICE" Atleast this is what I found. Not sure how you give them READ Rights to the GPO only. So I wanted to clarify what I found and what I think you meant.
Every services has recovery options that can be set (The recovery tab when loooking at a service.) Just set thisvia Group policy to restart on failure, that way even if they kill the exe then it restarts automatically.