It remind me when I was programming Windows Services and they were also impossible to stop using the windows Task Manager.
For resolving this we had to find a code called EnableDebugPrivAndRun.cpp, compile it to an executable and then launching the Task Manager with:
C:\>EnableDebugPrivAndRun.exe TaskMgr.exe
With that, the Task Manager was able to kill any process. Beware: even the Windows core processes can be killed (like lsass.exe in Windows 2000) and you just get a frozen machine).
You can still find the code and full article in that Microsoft article. The code is available when you click the link called Figure 3.
I used that long time ago, on Windows NT4 and Windows 2000 machines, I am not sure that will still works for the latest version of Windows and perhaps now such a tool would be provided by Microsoft's latest development environment.
UPDATE:
Apparently some other users found a solution in this SuperUser question and I also found a Windows Debugging Tools which contains a kill command which should do the job as well.
Extract of the MSDN site:
Debugging Tools for Windows (WinDbg, KD, CDB, NTSD)
3 ways to get Debugging Tools for Windows:
As part of the WDK Install Microsoft Visual Studio and then install
the Windows Driver Kit (WDK). Debugging Tools for Windows is included
in the WDK.
As part of the Windows SDK Install the Windows Software Development Kit > (SDK). Debugging Tools for Windows is included in the Windows SDK.
As a standalone tool set If you want to download only Debugging Tools for Windows, install the Windows SDK, and, during the installation, select the Debugging Tools for Windows box and clear all the other boxes.
The Debugging toolkit is available here.