Edit: I still had issues after trying everything because my Google accounts would not sync. I installed Samsung Email and was able to get notifications that way, so I deleted and re-added my Google accounts and, voila, notifications started working again. Give it a try if nothing else is working.
So, I had the exact same issue after going through all the steps where nothing worked. This is kinda dumb, but I went to settings > storage > clear all data. Then, I reopened the app and clicked "Allow Notifications". At the top, there was a informational notice telling me that sync was off, so I clicked that and told it to download all messages. I'm now getting notifications for everything. Not sure why, but maybe you can try the same if nothing else works...
