You do not need to use foreground notifications for an AccessibilityService to stay running in the background. It is a special case of Service.
The framework will attempt to automatically restart your accessibility service if it crashes. If it crashes multiple times, it will take longer each time to restart. This may be why it appears that your service is enabled, even though it is not running.