I have installed many of our custom written services on windows boxes (does not matter if XP, Server, Vista). I always configure to "Restart the Service" on 1st, 2nd and subsequent failures. But I have never seen this work; the service simply stops (because of an error or something in the code) but does not restart.
I just noticed the "Enable Actions For Stops With Errors" checkbox. Does this have to be checked in order for the recovery to take affect if the failure was caused by an error?