My experience is that services sometimes launch sub processes and at times the main program may terminate, but the other programs continue to execute which prevent the service from restarting.
Download and run Process Explorer. process-explorer
Process names will be indented by process parent. Here SearchInder.exe has launched 2 sub programs.
You need to find any orphan processes associated with your service and terminate them. If the parent has terminated, then the orphan's name may be in the left most column of the display.
Look at a test server that is running the same software and see what the process tree looks like.