Android Firebase Messaging calling getToken too soon after starting service?

I think I designed my use of Firebase Messaging in my Android app in a way that recently caused a problem.

When a user indicates he wants to receive messages, I then start my FirebaseMessagingService and immediately go get the token in my Activity:

Intent i = new Intent(this, myFirebaseMessagingService.class);
startService(i);

FirebaseApp.initializeApp(this);

FirebaseMessaging.getInstance().getToken().addOnCompleteListener(new OnCompleteListener<String>() {
    @Override
    public void onComplete(@NonNull Task<String> task) {
        if (task.isSuccessful()) {
            // send token to server...

A large number of devices recently did not get a token the first time using this method. The second time the user went to this Activity, the service was already running, so the devices got their token successfully using the same method.

Am I right that the token isn't generated the first time because I'm calling getToken() too soon after starting the service? (I have not been able to reproduce this while debugging.)

If so, I'm thinking the solution is to just start the service when the app is launched, so that by the time the user gets to this Activity, the token can be obtained successfully.

(Another possibility is that the service fails to start the first time but does start the second time, but I'm not sure why or how to detect that.)

Note the app is using Firebase Messaging version 22.0.0. I need to update it, of course, but I'm not sure the latest version solves this problem.

Thanks for any advice and feedback!