Is an android service guaranteed to call onDestroy()?

I'm not sure where you're seeing that a Service is guaranteed to have onDestroy() called. As far as I know, this isn't the case. If you read this page of the docs, it describes the conditions in which a service could be killed. So if you're asking if a process which hosts both an activity and service is being killed, will onDestroy() be called on the service (but not on the activity) then the answer is no; a service's onDestroy() will not necessarily be called. As to whether a service-only process can be abruptly killed by the OS: yes, it can. This is especially true when you have a lot of work to do, and your onStartCommand call only queues up the work to do asynchronously. Then the service will be spending the majority of its time not in the protected onCreate, onStartCommand or onDestroy methods.

There are two things to consider:

1. Android might decide to shut down a process at some point, when memory is low and required by other processes that are more immediately serving the user. Application components running in the process that's killed are consequently destroyed. A process is started again for those components when there's again work for them to do. Source

   In this case onDestroy() is not called as the Android OS will reclaim resources anyway (this is a basic task of the OS in general).

2. A service can be both started and have connections bound to it. In such a case, the system will keep the service running as long as either it is started or there are one or more connections to it with the Context.BIND_AUTO_CREATE flag. Once neither of these situations hold, the service's onDestroy() method is called and the service is effectively terminated. All cleanup (stopping threads, unregistering receivers) should be complete upon returning from onDestroy(). Source

   So when the Android OS notices that the Service has finished its job and is not needed anymore it will be destroyed. The OS gives the app a chance to release the Service's resources to prevent memory leaks. In this case onDestroy() is called as this is the place where the app can release its resources. Of course in this case the application's process stays untouched (as there may be other Services/Activities running in it).