1) Take a look at the developer docs page on status bar notifications. Also note that you'll want to look at the FLAG_NO_CLEAR constant, which should cover your condition.
2) Keeping the icon isn't necessarily a bad thing in the case where the app is killed, and somewhat depends on the purpose of the app. In particular, if your app goes into the background and then gets killed, leaving the icon has actually been noted to be expected behavior by one of Google's engineers:
Correct, onDestroy() is not called
when it is killed. This is the same
as activity -- the kernel kills
processes when needed, not waiting for
the app.
The status bar is correctly keeping
the icon. The service will later be
restarted; it has not been stopped.
It is normal for background services
to be killed regularly. This is
intentional, because generally
background services are not something
the user is directly aware of, and
restarting their processes every now
and then avoids issues with such
services consuming increasing amounts
of RAM.
If your service is something the user
is actually aware of (such as music
playback), consider
Service.startForeground().
That being said, the icon should probably disappear anyway. Other apps with persistent icons (Meebo comes to mind) will clear away if you kill them with a task manager. I'm not certain if this happens in all cases, though. If your app gets killed while in the background by the OOM, then you most likely won't want to clear it anyway.