sorry, da hatte ich mich etwas unklar ausgedrückt...
onDestroy() passiert tatsächlich irgendwann viel später - nämlich wenn Android Speicherplatz braucht. Und das kann Stunden später sein. Und dann auch gerne für mehrere alte Instanzen auf einmal.
Was aber auf jeden Fall vorher aufgerufen wird (wenn du die Methode implementierst), ist onPause()- und zwar genau dann, wenn die aktuelle Activity nicht mehr sichtbar ist und etwas anderes angezeigt wird.
In onPause() solltest du den Code eintragen statt in onDestroy(). Entspechend solltest du den Service in onResume() aktivieren.
Infos dazu findest du in der Android-Doku.
Und ich schreibe das super.onDestroy() immer am Ende von onDestroy() - ich will erst selber was machen, bevor mir die Superklasse dazwischen fummelt.