AndroidアプリのPush通知でFCMトークンが更新された場合の挙動について

Question

前提

Android Studio 3.3
Java8
firebase-messaging v17

質問内容

FCMの新しいトークンが発行されるとFirebaseMessagingServiceのonNewTokenが呼び出されますが、
この動作は、アプリケーションが起動中のみの挙動なのでしょうか。

FCMのガイドでは、トークンの変更は以下タイミングで行われるとされています。

• アプリによってインスタンス ID が削除される場合
• アプリが新しいデバイスで復元される場合
• ユーザーがアプリをアンインストール / 再インストールする場合
• ユーザーがアプリのデータを消去する場合

アプリのデータを消去した場合や、アプリを新しいデバイスで復元(Googleアカウント等を使用した復元？)した場合などは、
アプリを再び起動するまでonNewTokenPushが呼び出されず、通知が届かないということになるのでしょうか。

質問の背景
アプリをインストール済のユーザに対して、(通知が許可されていれば)必ずPush通知を送信したいという要件があります。

よろしくお願いいたします。