I believe that this issue was caused by the service itself.
It is highly probable that the service has bug and hang, fail, or take too much time to stop properly. Which raise issue when try to start it.
If the service fail:
In my opinion, there is a potential workaround,by setting up a service recovery option in the service properties. Then select "Run a program" when the service failed.
Then code a batch to get the PID of this service and kill it, then use NSSM to start it again.
In this batch you may use "SC query" command to check the service status:
C:\Windows>sc query "MyService" | find "STATE"
STATE : 3 STOP_PENDING
Note that if you use NSSM only to hide the windows, you may achieve the same goal with the Task Scheduler only.
In the "General" tab on task property. If you select "Run whether user is logged on or not", this will run from session 0 which won't show any window to you.
Then what you need to do on your scheduled task are, to kill / restart the target process itself as you do now. This will work more robustly.
If the service is not an official windows service but more an EXE program file (dev on your side) then converted to a services with NSSM, there is a high chance of failure.
It could be better to rewrite/recompile the program as an actual Windows service.