Написал приложение с сервисом. Сервис работает нормально.
Если таск киллером убить приложения, с ними вместе убивается и сервис, но через несколько секунд запускается заново системой.

Проблема в том, что если сразу после "убийства" перевести в режим ожидания (экран выключен), то сервис запустится только когда телефон перейдёт обратно в активный режим.