After a long struggle and feedback by several very helpful testers I think that I have found a reliable way to implement a CompanionDeviceService with startObservingDevicePresence.
In regard to your question, the behavior differs wildly across different Android versions and I highly recommend to test it on several devices. However, you should in any case start coroutines to handle your communication and (if applicable) show a notifiation to act as a foreground service and only use onDeviceAppeared as a launcher and onDeviceDisappeared as a hint on when to clean up.
However, things are complicated, so allow me to use this to share all my findings.
For a few months now I am working on an open source BLE remote control for Sony cameras. I implemented it as a CompanionDeviceService and rely entirely on startObservingDevicePresence to start it. At the time of writing this, Android 15 is the most recent OS and I support a minimum of Android 12 (earliest startObservingDevicePresence). I am running a public beta and am confident about it enough by now to hopefully do a "proper release" in 1-2 weeks.
So, all of the following refers to BLE and you can find the code and user feedback I refer to on github.
I have tested my app on a Pixel 6 with Android 15, a Pixel 3 with stock Android 12 and various LineageOS 20/21 images and on a few other Android 12 devices. I also got some logs from users with Android 14 devices and a Pixel 9 Pro with Android 15.
Across these devices I have found at least 4 different patterns for the onDeviceAppeared/onDeviceDisappeared callbacks:
Android 12:
If the device is already on, onDeviceAppeared is called immediately after startObservingDevicePresence, but there is no matching onDeviceDisappeared when it is turned off for the first time. Turning the device on again, reliably triggers an onDeviceAppeared and turning it off again triggers onDeviceDisappeared within a few seconds.
Android 13 and early Android 14:
These generate a single onDeviceAppeared event when the device is turned on, but it takes at least 2 minutes (sometimes even 3 minutes) until onDeviceDisappeared is called.
Later Android 14 and Android 15:
At some point, the 2 minute delay was removed and the behavior once again changed fundamentally. Now, onDeviceAppeared is called twice with two matching onDeviceDisappeared. As I found in the Android source and got confirmation on the Android issue tracker these correspond to internal calls to onDevicePresenceEvent with different event types EVENT_BLE_APPEARED and EVENT_BT_CONNECTED (and EVENT_BLE_DISAPPEARED and EVENT_BT_DISCONNECTED respectively). So, you will get an onDeviceAppeared when the device is seen in a scan and another onDeviceAppeared when you connect to it (not sure why that should be of any help). Similarly, the first onDeviceDisappeared corresponds to a disconnect and you get a second one when the device stops appearing in scans (after a little timeout).
Android 15 / Pixel 9 Pro:
If I had not seen the log of a Pixel 9 Pro I would not have believed it, but one of my users has seen another entirely different behavior. On his device, onDeviceAppeared is called twice as mentioned above, but then onDeviceDisappeared follows reliably after 10 seconds while the device is still connected and working. This may be partly a problem with this Bluetooth device (different camera model), but the connection does not drop and hence I don't think the call to onDeviceDisappeared is warranted. The device remains functional until it is really turned off, when onDeviceDisappeared is called a second time.
onDeviceAppeared and onDeviceDisappeared and map a simple connect/disconnect or service start/stop to it.onDeviceAppeared and last onDeviceDisappeared) are relevant. The other ones are much clearer communicated in onConnectionStateChange of your BluetoothGattCallback.The best solution seems to be to use the "outer" onDeviceAppeared and onDeviceDisappeared events to start/stop a service, but handle actual Bluetooth disconnects and reconnects independently inbetween. I think that this is actually the intended way to use these events: As indicator for when to start or stop the service. In fact, I think that these indicate the time during which you have the priviledged state of a companion service and are very unlikely to be killed. But the very different ways the events occur on different Android version and the barely existant documentation makes it really hard to figure out what you can expect. Even worse, the additional events since late Android 14 mean that you will have to ignore some cases.
So, I ended up literally counting the onDeviceAppeared events to only react to the first onDeviceAppeared and the last onDeviceDisappeared. I initialize my Bluetooth classes and call connectGatt on the first onDeviceAppeared. I free resources and terminate the service on the last onDeviceDisappeared (although, I think that Android would kill it eventually anyway).
Inbetween I let the "autoConnect" parameter of connectGatt keep the connection alive and observe its state through onConnectionStateChange of my BluetoothGattCallback. Especially any online/offline notification for the user is based on this. I actually even remove the notification when the device disconnects, so the users sees my service vanishing immediately (even though on Android 13/14 it actually stays around for a few minutes). So far, this seems to work well enough.
Note that this is not perfect for the Android 12 case where there is no matching onDeviceDisappeared after the very first connection. If you need that, you might have to handle Android 12 separately, but otherwise this only means that your service will stick around a bit longer afer the first startObservingDevicePresence and will eventually be cleaned by the system anyway
Also note, that according to the response I got on the Android issue tracker things might become easier with Android 16 when you can directly use onDevicePresenceEvent instead, but it will be a while until enough users have Android 16 to rely on. So, readers from the future with your fancy flying cars: Is it now nice to write BLE apps for Android or do you have more yearly API changes to worry about as we have seen since Android 4?