I hit the same thing with an app installed from F-Droid and latest Home Assistant OS.
The reproduction is simple: reboot Home Assistant.
Android application seems to be unable to reconnect to the server after this, but killing application and starting again helps.
I had this issue too, tried loads off stuff to fix it, eventually nailed it down to my Samsung Galaxy watch. When I deleted the watch from Home Assistant Mobile App, notify worked again.
notify.notify is a catch all service call. Its recommended to create a notify group and use that to dictate which devices should get the notification instead of trying all of them 
You are a genius. Removed my TicWatch and notify started working again. Thanks for the post
After OS upgrade to Android 13 (and on a different device) it works, not sure if it is related or not, but I no longer have this issue.
This issue is now fixed in the latest version of the Wear OS app. There was a bug where the watch was registering as a local push device which it is not. It has since been fixed now that official notification support was added to Wear OS.