You should consider approaching your problem from a different direction.
Trying to infer when the system has killed your Service is a problematic. Apps (Services) are not notified when they are terminated, therefor detecting this condition is difficult. However, finding out when a Service has started is trivial (onCreate()). This is a clue to the right approach.
It's clear that you understand that the proper way to exchange information between an Activity and a Service is via a binding. This is the other critical piece of the solution.
SOLUTION
You should expand the lifetime of your Service. Right now, it appears that you create the Service for the express purpose of conducting a long-running task. The Service is created when you want the task to start, and terminates as soon as it ends. In other words, the scope of the Service and the "task" are the same.
Instead, you should make the "task" a child of the Service; the Service should exist for somewhat longer than the "task". In particular, the Service should be available whenever the Activity is started (if for no other reason than to communicate information about the state of the "task" to the Activity).
Whenever the Activity starts, it should bind to the Service, and register a listener with the Service. The Service calls this listener whenever A.) the listener is newly registered, or B.) the "task" changes states (starts or stops). Thus, the Activity is always informed instantly of state changes, so long as it is bound to the Service.
When the Activity wants the "task" to change states, it should inform the Service via the binding (or possibly a startService() call, even though the Service is already running). The Service would then start/stop the background thread (or whatever it is you do to accomplish the "task"), and notify any listeners.
If the Service has been running the "task" for some time, and the Activity pops up all of a sudden, then the Service clearly knows the "task" exists, and the Activity will get that information via the listener, as soon as it binds.
When the Activity stops, it should clean up by unregistering its listener, and unbinding from the Service.
This approach obviates the need for SharedPreferences, or to detect when the Service has stopped. Whenever the Service is created, obviously the "task" is not running, so the Service will always know the correct answer to give to the Activity. And since the Service must be created before it can bind to the Activity, there is no order-of-operations problem.