Androidを初期化してから各種アプリの通知がこなくなりました。
かなり時間がかかりましたが解決しました。簡単にメモします。
【結論】
Androidで使うGoogleのメインアカウントを初期化直後に登録していなかった。
【時系列】
・電池持ちが悪いので初期化を決心
・ついでにGoogleアカウントを変更することに
・いざ、Androidを初期化
・初期設定で以前使っていた旧Googleアカウントを登録してアプリをダウンロード（ストアのマイアプリからDLできて便利なため）
・そのGoogleアカウントを消して新Googleアカウントを登録
・新アカウントでAndroidを利用していたところ、いろいろなアプリの通知がこなくなっていると気づく
・何週間かひたすら試行錯誤
・再度初期化をしても改善されず心折れかける
・だけどもう少しがんばる
・調べ回った情報の断片を総合するとメインで使う新Googleアカウントを最初に登録する必要があると予測
・三度目の初期化で上記を踏まえ設定し、解決
【推察】
Androidは端末の初期設定時に最初に登録したGoogleアカウントがメインアカウントになっているような気がします。
通知設定はそのメインアカウントに紐付けられているのだと思います。
通知が来なくなったという方でAndroid端末のGoogleアカウントを変更したことがある方はこれに該当しているかもしれません。
【参考】
上記の理由でAndroidの通知がこなくなった場合には初期化をしなくても「Googleサービスフレームワーク」のキャッシュ・データ削除、アップデート削除・再更新でも直るかもしれません。
また、GooglePlay開発者サービスのキャッシュ・データ削除をおこなうだけで通知が改善されるケースもありそうです。
【補足】
調べた限りでは、通知が来ないといっても様々なケースがあるようです。
・Wi-fiの設定が原因で通知がこない→モデムのAAAA送信抑制エラー応答機能を有効にする
・モバイルネットワークで通知が来ない・遅い→格安SIMなどのMVMOで発生するらしく、Googleサーバーとの接続が途絶えていることが原因なので対策アプリを使う
【余談】
端末の初期化というのは大変ですが、いろいろ調べ回るのに時間がかかり結局改善せず、また調べ直す……ということを繰り返すよりは、いさぎよく初期化してしまったほうがよいと今回思いました。今はバックアップのシステム（Googleドライブなど）も整備されていますし。
【おまけ】
今回通知がこなくなったことで、いろいろと検証するために「Push Notification Tester」という通知テストアプリを使いましたが、どうやらこのアプリの通知はAndroidの「TALK」というアプリを無効にしていると届かないようです。
以上です。