Use the Task manager to find the Service and kill it from there using End Task. Always does the trick for me.
If you have made the service yourself, consider removing Long running operations from the OnStart event, usually that is what causes the Service to be non responsive.