Now that 4.3 is out, something worth mentioning --
We discovered that there have started to appear applications abusing the Service.startForeground() API -- which is http://developer.android.com/reference/android/app/Service.html#startForeground(int,%20android.app.Notification)
-- to make their application unkillable without the user knowing.
They were doing this by creating a carefully malformed Notification object that resulted in the notification manager not posting the notification, even though the activity manager thought things were fine and so allowed the service to go in the foreground state.
Originally we were going to solve this by just being better at detecting this kind of malformed notification, and crashing the app like we do on other bad notifications. Unfortunately, there are too many applications doing this for that to be a viable approach.
Instead, what we ultimately did in 4.3 is have the system put up its own notification when it detects this so that the user is aware of what is going on and the app doesn't have incentive any more to do this.
If you have an application that has been doing this, you'll want to update your app to stop doing it, so your users don't see the less-than-optimal generic system notification it creates for you.