They ask the push providers (Apple/Google) for data on the push token from e.g. a messaging app. This way they associate the account from an app with an identity.

Very overlooked point. You can find privacy guides online but very few even suggest that FCM etc. might have privacy issues, let alone explain exactly why. It seems this has already been used by law enforcement in the past: https://www.wired.com/story/apple-google-push-notification-surveillance/

The Molly-FOSS fork of Signal (which aims to be even more secure/private) actually supports self-hosted push notifications using UnifiedPush.

I also found this comment:

As far as I know, FCM on Android can be configured to use a notification payload (which is piped through Google’s servers). But for a release app this is discouraged, especially if you are privacy conscious. An app would normally use FCM to receive a trigger and look up the received message from the app’s own backend. See here for more information.