Here's the hidden mystery setting area:
1. Settings
2. type in "background apps"
3. toggle "on" for all apps that need to behave, such as "messaging"
Worked for me when this occurred following a phone update and persisted following a subsequent phone update and despite trying every solution out there on the internet. This solution seen on other sites and sharing here since it seems to help.
Note to Microsoft: do not remove phone settings when updating the phones, thanks