Thanks to everyone for getting involved in this discussion.
I've collected some more data. After installing ntfy for better control of FCM, I can confirm that High and Max priority notifications work fine while in Doze, while Normal or lower priority exhibits this same behavior.
I also realized that i had microG Services installed (to use Revanced Youtube), and thought it might've been conflicting with how Play Services handles notifications in some way. I uninstalled it, cleared storage for Google Play Services, Play Store, uninstalled Gmail, then rebooted my phone, logged back into my accounts and reinstalled Gmail from Play Store. Now I'm not getting notifications at all from Gmail anymore.
It feels I've left my phone in this dirty state and the only way to really isolate the issue is to perform a factory reset. It sucks, but I don't know what else to do. I will report back with results when I have time to do this.
Meanwhile, can anyone confirm that Normal priority notifications get pushed immediately (or close to it) while the device is left discharging and stationary for several minutes (in Doze)? Or is it only supposed to happen during the normal Doze maintenance windows?
From Android's official docs:
For messages that don't result in notifications, such as keeping app content up to date in the background or initiating data syncs, use normal priority FCM messages. Normal priority messages are delivered immediately if the device isn't in Doze. If the device is in Doze mode, they are delivered during the periodic Doze maintenance windows or as soon as the user wakes the device.
It seems this lines up with what I've been seeing on GrapheneOS, but I haven't observed this on other Android devices I've used. Even if they're supposed to be delivered during maintenance windows, I don't think that explains why I've been seeing 1h+ old notifications delivered only when I've unlocked the phone. I wonder if these windows get so infrequent for this to happen, or if the way maintenance works is broken on my setup.
Either way, this seems wrong. A phone should be able to notify me when something happens, not wait until I explicitly unlock it.