[org.thoughtcrime.securesms] Signal Push notifications not working

Affected app
Name: Signal
Package id: org.thoughtcrime.securesms

Describe the bug
Push notifications won't work with Signal, they are unreliable and won't notify when Signal is running in background. Notifications are shown as soon Signal is opened manually. Signal is registered correctly in MicroG GCM, Push notifications from other Apps are working.

To Reproduce
Steps to reproduce the behavior:

1. Install MicroG and enable Device Registration + Cloud Messaging
2. Install Signal from PlayStore and register
3. Send a message to your newly registered Signal account from another Smartphone
4. See error, push notification won't be shown until Signal app is opened

Expected behavior
Receive Signal notifications immediately

System
Android Version: 11
Custom ROM: CalyxOS 2.8.2

microG
microG Core version: 0.2.22.212658-47 (4e6d091)
microG Self-Check results: All ticked

Additional context
Problem was reproduced many times and I did completely uninstall Signal and wipe MicroG data. When doing so, multiple reboots were enforced after activating Device Registration and Cloud Messaging. Re-installing Signal shows me that it's added correctly to Cloud Messaging, sadly it didn't fix the problem.

No source file or test is named. Start by reproducing the issue using the listed Android 11, CalyxOS, Signal, and microG versions, then trace the Device Registration and Cloud Messaging paths. Done means Signal receives push notifications while running in the background, without opening the app.