This can be fixed by adding the following code snippet to the Android Manifest:

<manifest xmlns:android="http://schemas.android.com/apk/res/android" package="com.example.app">
  <queries>
    <package android:name="com.example.service" />
  </queries>

  <application>
    ...
  </application>
</manifest>

In SDK 29 it was working, but in SDK 30 and 31 bindService() returned always false and did not throw any exception. The system simply couldn’t find the service, even though the service was exported using android:exported="true".