Confirmed. It seems to appear because you restart the Starter service when the task has been killed (I have made the test removing the StartServiceAt and the layout reloaded). As Erel already told us, we should not start the Starter service by ourselves but let the activity / other service, restart it.
So, if you need to make background tasks, I recommend you to make them in another service and restart that one from the Service_TaskRemoved instead of the Starter. Again, Starter will be restarted by the other service by itself.
Edit: proposal attached