I had the exact same issue few days back Signal notifications suddenly stopped working
I tried multiple things, even reinstalled playservices and then the signal app(Signal app was not even recognizing play services installed and it was using its own way to receive notification), but nothing worked fine for me and finally i did a factory reset and everything is working fine now.
Before doing this i tried to update Google play services via play store then i saw its status was installing and never completed, i believe this was the issue, im not sure though.
This time onward i didnt enable the option to update play services apps via playstore. ill just use the GOS app for updating this.