BroadcastReceiver SMS_Received not working on new devices

Okay the problem was resolved.
The issue did not reside with priorities, but with my phone being a Nexus 6P (a.k.a. API 23).

Providing permissions in the manifest.xml alone wasn’t enough and I had to add code for runtime permission request. See Android documentation for runtime permissions

Add this code to your MainActiviy:

ActivityCompat.requestPermissions(this, 
            new String[]{Manifest.permission.RECEIVE_SMS},
            MY_PERMISSIONS_REQUEST_SMS_RECEIVE);

Define this at the top of MainActivity Class:

private int MY_PERMISSIONS_REQUEST_SMS_RECEIVE = 10;

And also add this override:

@Override
public void onRequestPermissionsResult(int requestCode, @NonNull String[] permissions, @NonNull int[] grantResults) {
    super.onRequestPermissionsResult(requestCode, permissions, grantResults);
    if (requestCode == MY_PERMISSIONS_REQUEST_SMS_RECEIVE) {
        // YES!!
        Log.i("TAG", "MY_PERMISSIONS_REQUEST_SMS_RECEIVE --> YES");
    }
}