Having the same issues here on my Pixel 7A, been going on for about 2 weeks now. Restarting the phone make all notifications that should have appeared, appear again. However, all new notifications are still very delayed.
I, too, have installed & enabled Google Play services with network permissions enabled + battery saving permissions to unrestricted.