To understand why this happens, we need to know that SQL Server employs co-operative multitasking. That is, every task yields approximately every 4 ms to permit other tasks to run. It is also at these breaks that a process finds out that has been killed. Yielding is nothing that happens automatically, but the yieldpoints are simply programmed into the SQL Server code.
But if a process needs to do work outside SQL Server, for instance an OS call, there is no way it can yield, because that external code does not have any calls to the SQL Server OS - it does not even know what SQL Server is.
So if a process gets stuck outside SQL Server, KILL will not help. What can help is if you can find where the process has actually been hung up, and try to kill the task on that end. One case where this is possible is if you are making a call to a linked server which gets blocked on the remote server. Killing the query on the local server is not going to help - but killing the process on the remote server will.
If this is something called through xp_cmdshell, maybe you can find the process in Windows.
Else, yes, reboot SQL Server.