I managed to get my notifications working again. I tried all sorts of things with no success until this last method. Here's the final method I did to fix it:
Logged into Facebook on my laptop and went to settings -> security -> "where you're logged in". I ended all of the sessions. Next I uninstalled Facebook then Messenger from my phone. Then, I held the power button to turn off the phone, turned it back on, then soft reset (power and volume down button for ~10 seconds).
When the phone booted back up I re-installed Facebook, then Messenger. I logged into Facebook, then logged into Messenger.
I turned the phone off once more, then back on, and I started receiving notifications for both apps. Shortly afterwards Messenger notifications stopped but the Facebook app was still receiving notifications for messages.
*** I did NOT use the Facebook app for messaging from the time that I re-installed it, as I suspect that the messaging in the Facebook app crosses wires somehow with Messenger, which I will get back to later. ***
I used only the messenger app and after about 20 minutes of not receiving notifications, it started notifying me for all messages without delay.
It's been working perfectly ever since.
I tried using the Facebook app for messaging to see if that would break Messenger again and, as I suspected, it did. I redid the method above to fix it and it worked perfectly again.
Let me know if you guys try this and get it working!
(and before anyone asks, yes I tried simply reinstalling and soft resetting alone, as well as a bunch of other methods; none of which gave me these results)