Android: Sticky Service won't restart

My app uses the Service for background tasks. I want the Service to keep running when the user kills the application (deletes it). There are two scenarios in which a user can kill an application:

Scenario 1: When in app:
    1 User presses **backbutton**, apps goes to background and user is on the homescreen.
    2 User presses the multitasking button and swips the app away.
    3 The Service should restart because its sticky.

Scenario 2: When in app:
    1 User presses **homebutton**, apps goes to background and user is on the homescreen.
    2 User presses the multitasking button and swips the app away.
    3 The Service should restart because its sticky.

      

        
        
        
      

    

Scenario 1 works exactly as expected. The service restarts after the app is uninstalled in a matter of seconds.

Scenario 2 doesn't work as expected. The service restarts, but after 5 minutes.

I don't understand why it takes so long to restart the service in scenario 2. Is there a known solution?

public class MainActivity extends Activity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        Intent test = new Intent(this, TestService.class);
        startService(test);
    }
}

public class TestService extends Service {

    @Override
    public int onStartCommand(Intent intent, int flags, int startId) {
        Log.e("Service", "Service is restarted!");//In Scenario 2, it takes more than 5 minutes to print this. 
        return Service.START_STICKY;
    }

    @Override
    public IBinder onBind(Intent intent) {
        return null;
    }
}