I have a foreground service and I starts it by:

context.startForegroundService(Intent(context, MyForegroundService::class.java))

In the service, it uses START_STICKY

override fun onStartCommand(intent: Intent?, flags: Int, startId: Int): Int {
    // do work...
    startForeground(ID, notification, ServiceInfo.FOREGROUND_SERVICE_TYPE_LOCATION)
    return START_STICKY
}

After the system kills the service (e.g. low on resources), it will try to recreate it later "from the background". Here we comes the problem for Anroid 12+ devices:

• If I call startForeground(), it gives me ForegroundServiceStartNotAllowedException
• If I don't call startForeground(), it gives me an exception for not starting the service on foreground within 10 seconds

In simple words, the service will crash no matter what you do. This seems to be an Android design flaw. It seems the only workaround is to use START_NOT_STICKY and schedule a WorkManager at onDestory() to do a lesser portion of the work. Am I thinking this right?

The docs say that a foreground service should be restarted properly.

Since Android version Build.VERSION_CODES.S, apps targeting Build.VERSION_CODES.S or above are disallowed to start a foreground service from the background, but the restriction doesn't impact restarts of a sticky foreground service.

Apparently there is a bug, or a series of bugs, that affects Android 14 and Android 15.

I can reproduce a similar bug in an API 35 emulator. When consuming RAM with a RAM filler app, the virtual screen of the phone goes black for a second, and a bunch of services are killed. When most services are restarted, the foreground service fails to restart with not allowed due to mAllowStartForeground false. I guess if the RAM fills too much, it triggers a bug which makes the Android system forget that the service was foreground.

If the RAM is filled carefully, just enough to kill the foreground service, then the service is properly restarted. If the service is directly killed (e.g. calling Process.killProcess(Process.myPid()) inside the app or kill <pid> in a rooted adb shell), then the service is properly restarted.

Workarounds

It might be possible to use the exemptions to avoid the bugged restriction if the app doesn't use location/camera/microphone.

For example, asking the user to turn off battery optimization for the app will help.
On Android 15 the menu is ridiculously well hidden. Need to click on the text of an unrelated option to make the full menu visible. Would be hard to guide the user to it.
It's possible to ask the user to turn off battery optimization with ACTION_REQUEST_IGNORE_BATTERY_OPTIMIZATIONS. That requires REQUEST_IGNORE_BATTERY_OPTIMIZATIONS permission, which requires a special use case to be allowed on Google Play.

Alternatively, the workarounds proposed here might help even if the app uses location/camera/microphone. I didn't test them.