18
If an application is forcefully terminated (e.g. through Task Manager), then Windows does not remove the notification icon. Windows Explorer doesn't even notice that the application has gone away until it attempts to send a message (usually a mouse movement message) to the window that owns the notification icon. At that point, Windows will remove the now dead icon from the notification area.
Given that you can't intercept TerminateProcess, there's nothing that your program can do about this by itself.
I guess that Windows Explorer could watch for the owner window being destroyed (as when the application quits unexpectedly), but it doesn't.
Even if the application is shut down gracefully, it must still remember to remove any of its notification icons. That is: if you don't call Shell_NotifyIcon(NIM_DELETE) (the equivalent of NotifyIcon.Dispose) when your application shuts down (even gracefully), the icon will remain there until the mouse moves over it.
Oh, and if this is a service process that's displaying the notification icon, be aware that session 0 isolation in Windows Vista and Windows 7 will break it.