According to the documentation here:
Multiple clients can bind to the service at once. When a client is done interacting with the service, it calls unbindService() to unbind. Once there are no clients bound to the service, the system destroys the service.
So maybe you're missing some unbind in one of your activities. You can check this by printing a log in the onBind and onUnbind methods of your service.