GCMNetworkManager isn't running PeriodicTask after reboot

The app shows expected behavior if the app is running in the foreground, background or killed. However, once it is rebooted the PeriodicTask stops running

Following are the relevant bits of code:

In AndroidManifest:

<uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED"/>
<service android:name=".tracking.MyTaskService"
            android:exported="true"
            android:permission="com.google.android.gms.permission.BIND_NETWORK_TASK_SERVICE">
            <intent-filter>
                <action android:name="com.google.android.gms.gcm.ACTION_TASK_READY" />
            </intent-filter>
        </service>

PeriodicTask config:

PeriodicTask task = new PeriodicTask.Builder()
                .setService(MyTaskService.class)
                .setTag(TASK_TAG_PERIODIC)
                .setPeriod(30L)
                .setFlex(10L)
                .setExtras(bundle)
                .setPersisted(true)
                .build();

        mGcmNetworkManager.schedule(task);

In the Logcat, I get the following:

E/NetworkScheduler.TED: Couldn't start service: Intent 
{ act=com.google.android.gms.gcm.ACTION_TASK_READY
  cmp=xxx.xxxxxx.xxx/.tracking.MyTaskService (has extras) 
}

Appending all relevant details:

AndroidManifest.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.google.example.gcmnetworkmanagerquickstart">

    <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED"/>

    <application
        android:allowBackup="true"
        android:icon="@mipmap/ic_launcher"
        android:label="@string/app_name"
        android:supportsRtl="true"
        android:theme="@style/AppTheme">
        <activity android:name=".MainActivity">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>

        <!-- [START manifest_service] -->
        <service
            android:name=".MyTaskService"
            android:exported="true"
            android:permission="com.google.android.gms.permission.BIND_NETWORK_TASK_SERVICE">
            <intent-filter>
                <action android:name="com.google.android.gms.gcm.ACTION_TASK_READY" />
            </intent-filter>
        </service>
        <!-- [END manifest_service] -->

    </application>

</manifest>

MainActivity

public class MainActivity extends AppCompatActivity {

    private static final String TAG = "MainActivity";
    private static final int RC_PLAY_SERVICES = 123;
    public static final String TASK_TAG_PERIODIC = "periodic_task";

    private GcmNetworkManager mGcmNetworkManager;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        mGcmNetworkManager = GcmNetworkManager.getInstance(this);

        if(checkPlayServicesAvailable()){
            startPeriodicTask();
        }

    }



    public void startPeriodicTask() {
        Log.d(TAG, "startPeriodicTask");

        PeriodicTask task = new PeriodicTask.Builder()
                .setService(MyTaskService.class)
                .setTag(TASK_TAG_PERIODIC)
                .setPeriod(5)
                .setPersisted(true)
                .build();

        mGcmNetworkManager.schedule(task);
    }

    private boolean checkPlayServicesAvailable() {
        GoogleApiAvailability availability = GoogleApiAvailability.getInstance();
        int resultCode = availability.isGooglePlayServicesAvailable(this);

        if (resultCode != ConnectionResult.SUCCESS) {
            if (availability.isUserResolvableError(resultCode)) {
                // Show dialog to resolve the error.
                availability.getErrorDialog(this, resultCode, RC_PLAY_SERVICES).show();
            } else {
                // Unresolvable error
                Toast.makeText(this, "Google Play Services error", Toast.LENGTH_SHORT).show();
            }

            Log.d(TAG, "Play Services NOT Available");
            return false;
        } else {
            Log.d(TAG, "Play Services Available");
            return true;
        }
    }
}

MyTaskService

public class MyTaskService extends GcmTaskService {

    private static final String TAG = "MyTaskService";

    @Override
    public void onInitializeTasks() {
    }

    @Override
    public int onRunTask(TaskParams taskParams) {
        Log.d(TAG, "onRunTask: " + taskParams.getTag());

        return doPeriodicTask();
    }

    private int doPeriodicTask() {
        Log.d(TAG, "doPeriodicTask Called");
        return GcmNetworkManager.RESULT_SUCCESS;
    }


}

build.gradle (App Module)

apply plugin: 'com.android.application'

android {
    compileSdkVersion 26
    buildToolsVersion "26.0.0"

    defaultConfig {
        applicationId "com.google.example.gcmnetworkmanagerquickstart"
        minSdkVersion 14
        targetSdkVersion 26
        versionCode 1
        versionName "1.0"
    }
    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'
        }
    }
}

allprojects {
    repositories {
        jcenter()
        google()
    }
}

dependencies {
    compile fileTree(dir: 'libs', include: ['*.jar'])
    testCompile 'junit:junit:4.12'
    implementation 'com.android.support:appcompat-v7:26.0.0-beta2'

    compile 'com.squareup.okhttp:okhttp:2.7.0'

    compile 'com.google.android.gms:play-services-gcm:11.0.2'
}

Edit1: After some days of analysis, I have figured out the following:

1. This is a device specific issue. Doesn't happen on nexus devices, for example.
2. This is part of a bigger issue. The devices showing this behavior also doesn't work as expected with AlarmManager, FirebaseJobScheduler and RECEIVE_BOOT_COMPLETED broadcast receiver.
3. One workaround is this solution. However, this solution has at least 2 issues. (1) When you kill the app, AccessibilityService permission is reset. Which means everytime you open the app after this, manually permission is to be given. (2) If the app is killed, reboots after that won't hit the RECEIVE_BOOT_COMPLETED broadcast receiver
4. Crazy finding: In one-plus devices, if your app has the word test in the package structure, everything works!!
5. If you whitelist your application going to settings > Apps (The location and name of this could be different in different devices), everything works as expected.
6. The start up apps to which you have to manually add your app contains well known apps such as WhatsApp, Facebook, Instagram and many others. When you install these apps, they get automatically added to this list! I'm yet to see a custom API published by any of these manufacturers for doing this. This makes me think that these apps are white listed from manufacturers' end.