どうもこんばんわ。
今日の私は憤慨中であります。

まぁ原因はタイトルにあるサービスについてです。
多分、OS4.3以降なのかですが

サービスが停止したあと再起動されません。

開発フォーラム
https://code.google.com/p/android/issues/detail?id=63793
https://groups.google.com/forum/#!topic/android-developers/H-DSQ4-tiac

これなにいってるかというと、システムが自動で停止したのも入ります。
ようは START_STICKY とか START_REDELIVER_INTENT してる場合でも再起動しないよってことです。

例えば

サービス稼働中 → 端末がメモリーいっぱいなので停止 → 端末が余裕できたので再起動


サービス稼働中 → 端末がメモリーいっぱいなので停止

になります。

確かにタスククリア等で明示的に行った場合はいらないものは再起動されなくなるのでいいのかもしれません。
でもシステム側で自動停止したものは再起動かけてよと。。。
てかSTART_STICKYとかってシステムがやばくなったら停止するよ。だけどそのあと再起動するからねって
あなたたちが言ってるんでしょうと。。。

なので START_STICKY とか START_REDELIVER_INTENT してもどっかで停止したら
直接アプリを起動するまで動かないので注意してください。

影響ですが

1.startforegroundでサービス起動
そこまで影響ないと思われます。ただ通知必須ですが・・・

2.ブロードキャストをフックして再起動かけれるサービス
頻繁に動かすサービスじゃなければ影響少ないかも。

3.内部でブロードキャストを設定したり定期的な監視のみのサービス
停止したら再起動しないっす。何もできません。。


ということで私のManageBoxでも思い切り3に該当するので影響受けました。
なので対策ですが開発フォーラムで抗議されまくりなもののとりいそぎの対応をしなきゃねってことで
ナイスな方が実機検証を下に対策方を上げております。

------------------------------------------
@Override
    public int onStartCommand(Intent intent, int flags, int startId)  {
    super.onStartCommand(intent, flags, startId);

    if(intent == null){
            return START_STICKY;
        }

      try{

           Intent restartServiceIntent = new Intent(getApplicationContext(),
                   this.getClass());
           restartServiceIntent.setPackage(getPackageName());
           PendingIntent restartServicePendingIntent = PendingIntent.getService(
                   getApplicationContext(), 1, restartServiceIntent,
                   PendingIntent.FLAG_ONE_SHOT);
           AlarmManager alarmService = (AlarmManager) getApplicationContext()
                   .getSystemService(Context.ALARM_SERVICE);
       
        //再起動タイミングは5秒間隔            
           alarmService.set(AlarmManager.ELAPSED_REALTIME,
                   SystemClock.elapsedRealtime() + 5000,
                   restartServicePendingIntent);

           super.onTaskRemoved(intent);
       }catch(Exception e){

       }
       
       return START_STICKY;
    }
-------------------------------------------------------

そこまで頻繁に再起動しないって方は間隔をあけるものいいと思います。

まぁ最後に言いたいのは
こんなふうにするならちゃんと情報を公開してください。
てか自分たちのアプリ(Google)だけ再起動されてるせいもあり
かなり開発者フォーラムでは騒がれておりますけど・・・

ということでとりあえず抗議はされまくってるけど
今後どうなるかわからないのでご注意を・・・