When Nautilus stopped responding and couldn't be killed, it turned out I had sshfs hanged. So this helped to kill it:
killall sshfs
When sshfs hangs, it sometimes causes a file browser to hang in such a way that it cannot itself be killed, but sshfs can still be killed. Killing sshfs in this situation makes it possible to kill (and restart) the file browser. Sometimes the file browser will quit when sshfs is killed; occasionally it might even start responding immediately and not have to be killed.
This does not always work, of course, because when a file browser such as Nautilus hangs, even in the specific scenario described here where kill -9 was ineffective, it is not always due to a problem with sshfs. However, this does seem to be a fairly common cause of the problem.
Killing sshfs also stops other filesystem activity through sshfs mounts. When sshfs is malfunctioning, you probably want that. When it's not, and some other problem is hanging your file browser, you may not.
When a process can't be killed, even with SIGKILL, even by root--which is what the question here describes happening to nautilus--it's usually because the process is stuck in uninterruptible sleep (see also 3dGrabber's comment).1
It's normal for a process to enter uninterruptible sleep for very short periods of time. Processes communicate with the kernel through system calls. Some system calls, while executing, cannot be interrupted by signals, so any signals sent to the process must wait until the system call has completed. Normally, that happens, and then the signal is received. But when a system call that can't be interrupted hangs, the process can never receive a signal, unless the hang can be stopped through some other means.
Killing a process is achieved by sending it a signal. By default, the kill command sends SIGTERM, which processes are free to handle however they want and is thus sometimes ineffective. The harsher way to kill a process is SIGKILL (which kill -9 or kill -KILL sends). Processes cannot choose to ignore SIGKILL, but they still do not receive it while in uninterruptible sleep.
A common cause of prolonged uninterruptible sleep is malfunctioning drivers, including filesystem drivers. Drivers are often implemented as kernel modules, and while most kernel modules can be loaded and unloaded, once one is malfunctioning and unable to complete an operation, there is often no reasonable and safe way to force it to stop while continuing to use the system. To end a process that's stuck in uninterruptible sleep, it's usually necessary to reboot.
FUSE drivers are a major exception to this. When they malfunction, you often needn't reboot. With FUSE, the details of how a filesystem is accessed are implemented outside the kernel, in an ordinary program. To access data on a FUSE filesystem, a program will still make system calls, but the kernel delegates them through the FUSE module into a handler program.
sshfs is a FUSE filesystem driver. When data are accessed on an sshfs mount, a system call is performed that delegates work to an sshfs process. (Behind the scenes, to mount an sshfs filesystem, /usr/bin/sshfs was run. Or you may have run the sshfs command manually.) If this malfunctions, it can cause the program attempting to access the sshfs filesystem to remain in uninterruptible sleep, yet the sshfs process itself may remain killable. When that process is killed, the system call becomes unstuck, returning an error code to indicate failure, and the program that made the system call can terminate or continue running.
Malfunctions causing prolonged uninterruptible sleep are not unique to sshfs. They can happen with any filesystem, FUSE or not, though if it's not a FUSE filesystem then you likely must reboot. And there are other commonly used FUSE filesystems where this could occur, such as ntfs-3g. It doesn't happen often with any filesystem, but in practice it seems to occur more often with sshfs than most other FUSE filesystems.
Any program making a system call that uses a malfunctioning filesystem driver could run into this. But you would usually at least be trying to access a file on an sshfs mount, and thus have some idea of what might be wrong. In contrast, file browsers frequently access data outside of where you are currently working, in order to avoid giving outdated information about things like what filesystems are currently mounted and how much space is available on them, and sometimes to fetch information in the background to build thumbnails.
1 Another scenario where this could happen is when it's a zombie process. However, unlike a process stuck in uninterruptible sleep, a zombie processes rarely causes problems, since the only resource it takes up is a row in the kernel's process table. A zombie nautilus processes would typically go unnoticed. In particular, that shouldn't keep a subsequently executed nautilus process from managing the desktop.
