It is counterintuitive, feels arbitrary, and logical thinking will cause you to misread the chart they provide. Whether that method is called is based on the payload of the notification as well as making sure you've properly registered the types of notifications. This is helpfully spread between Android docs and the Firebase docs. The exact differences between the notifications that will trigger this (while still being compatible with iOS) is left as an exercise to the reader.
It's not that bad if you completely ignore Firebase and override onHandleIntent. Now you can choose what to do with the message without caring about the difference between "data" and "notification" messages or whether your app is in the foreground.
Can you elaborate on this a bit? Is it possible to use a non-Firebase push notification service on Android, that properly works in the background? Our the app still needs to use FCM but you can override the client-side handler somehow?
Both are possible. The source code to the Firebase push messaging service is available on Maven and GitHub, so you can re-implement it. Otherwise, you subclass the same service but override `onHandleIntent` instead of `onMessageReceived`, and avoid the code path that immediately displays the notification for 'notification' messages when the app is in the background.