FirebaseInstanceId: background sync failed: TIMEOUT

My Application uses FCM notifications, but the FCM registration is very unreliable as it fails a lot of times. This happens only on few devices (like Nokia 6 with Android 7.1.1), but again, this doesn't happen always. When the server tries a push notification, it says "not registered".

Code -

public class XCFirebaseInstanceIDService extends FirebaseInstanceIdService {
@Override
    public void onTokenRefresh() {
        // Get updated InstanceID token.
        String refreshedToken = FirebaseInstanceId.getInstance().getToken();
        // If you want to send messages to this application instance or
        // manage this apps subscriptions on the server side, send the
        // Instance ID token to your app server.
        sendRegistrationToServer(refreshedToken);//custom call to server to register token
    }

FirebaseInstanceId.getInstance().getToken() - this line gives following error on logcat -

D/FirebaseInstanceId: background sync failed: TIMEOUT, retry in 40s

Please note, error is TIMEOUT, and NOT other type of other FCM errors as most reported.

Manifest -

    <service
        android:name="com.xxxxx.fcm.XCFirebaseInstanceIDService">
        <intent-filter>
            <action android:name="com.google.firebase.INSTANCE_ID_EVENT"/>
        </intent-filter>
    </service>