I had this problem on two Moto X4's after upgrading to Pie. After some time and factory resets, I started getting notifications from Outlook app that had been missing, but Play would not auto-update on the phone set to, and would not notify of updates on the phone set to notify only.
Finally I started on mine to go through developer options. Still no luck.
I even created a shortcut to settings widget on desktop to show the notifications log. No sign notifications were ever happening.
Finally, I went back and started digging through advanced settings. Here's what finally fixed it (confirmed on my wife's phone as well).
1) Settings...
2) Apps and notifications...
3) Advanced...
4) Special App Access...
5) Notification Access...
Here's where the two phones differed. Mine had Moto Launcher, Microsoft Launcher, and Android Setup enabled.
The other phone had two Android Setup enabled plus Moto Launcher.
When toggling these off and back on are some interesting comments about how this can allow apps to do things with notifications.
In the end, we found that turning off this setting fixed it temporary, till the next restart, but the Android Setup would have this enabled again. When we went to apps.. show system... And disable Android Setup.... It continues working across restarts... What I don't know is whether there is any I'll effect in having Android Setup disabled.
We are getting play notifications (my phone)/ auto updates (hers).
Interested to know if this workaround solves the issue on Pixel..