Aby serwis działał cały czas, z tego co wiem, musi być FOREGROUND.
Notification notification = new Notification();
startForeground(1, notification);
Obiekt Notification możesz rozwinąć, bo to będzie się cały czas wyświetlać na górnym pasku androida.
A jeszcze możliwe, że masz w telefonie taki wbudowany system oszczędzania energii. Ja tak miałem w Huawei, ale znalazłem w Ustawieniach telefonu, w zakładce Oszczędność Energii możliwość dodania wyjątków do niektórych aplikacji. Chodziło o to, że telefon sam wyłączał wszystkie nieużywane przez użytkownika serwisy w celu oszczędzania energii.