※Pixel 5 Android 12 betaでほぼ確実に発生することを確認しましたが、他の端末・バージョンだと発生するかどうかはまちまちです。

Foreground Serviceを実行している間にアプリをタスクキル（タスクリストからActivityをスワイプして消す）すると、ServiceのonDestroyは呼ばれず、Foreground Serviceの通知が残り続けます。

LogCatを見ていると

ActivityManager: Scheduling restart of crashed service

のような行が見えます。おそらくタスクキルの操作により一度Serviceが強制停止されるが、システムにより自動的にServiceが再起動されているのでしょう。

以下のようにログを仕込んで、タスクキル時にServiceに何が起こっているかを調べてみました。

class MyService : Service() {

  override fun onCreate() {
    Log.d("HOGE", "onCreate")
    super.onCreate()
  }

  override fun onDestroy() {
    Log.d("HOGE", "onDestroy")
    super.onDestroy()
  }

  override fun onStartCommand(intent: Intent, flags: Int, startId: Int): Int {
    Log.d("HOGE", "onStartCommand")
    // Serviceで行う処理
  }
}

すると、タスクキル操作をした後に以下のログが出ていました

10-13 11:46:34.649  1741  3928 W ActivityManager: Scheduling restart of crashed service my.app/my.app.MyService in 1000ms for start-requested
10-13 11:46:35.661  1741  1892 I ActivityManager: Start proc 28886:my.app/u0a522 for service {my.app/my.app.MyService}
10-13 11:46:37.281 28886 28886 D HOGE: onCreate

このログから、以下のことがわかります。

タスクキル操作によりonDestroyは呼ばれない
Serviceがシステムにより再起動されonCreateが呼ばれる
再起動時はonStartCommandは呼ばれない

タスクキルをしてもForeground Serviceは動き続ける（一旦止まるがシステムにより再起動される）ので、通知が消えないようです。

解決方法

シンプルにタスクキル操作時にServiceを止めたいという場合は、AndroidManifest.xmlにandroid:stopWithTask="true"を付ければ良いです。

<?xml version="1.0" encoding="utf-8"?>
<manifest
    xmlns:android="http://schemas.android.com/apk/res/android"
    package="my.app"
    >

    <uses-permission android:name="android.permission.FOREGROUND_SERVICE" />

    <application>
        <service
            android:name=".MyService"
            android:exported="false"
            android:foregroundServiceType="microphone"
            android:stopWithTask="true"
            />
    </application>
</manifest>

Serviceを止めるだけでなく、なんらかの処理を行いたい場合はandroid:stopWithTask="true"を付けずに（または"false"を付ける）ServiceでonTaskRemovedをオーバーライドします。

class MyService : Service() {
  override fun onTaskRemoved(rootIntent: Intent?) {
    // タスクキル時の処理
    // Serviceを止めたいならstopSelf()する
    // super.onTaskRemovedは空なので、呼ばなくても大丈夫そう。将来仕様が変わる可能性を考慮して一応呼んでおいたほうが安全かも？
  }
}

ただし、onTaskRemovedが呼ばれるのはServiceがシステムにより再起動された後です。すなわち、一度Serviceは強制停止された後、新しいServiceが開始され、そのインスタンスでonTaskRemovedが呼ばれます。ちょっと直感的ではない動き方なので気をつけましょう。

タスクキルする
Serviceが強制停止される（onDestroyは呼ばれない）
システムによりServiceが再開される（onCreateが呼ばれる）
onTaskRemovedが呼ばれる

onTaskRemovedが呼ばれる時点ではServiceのインスタンスが作り直されているので、注意しましょう。「Serviceのインスタンスは一つだけ」というつもりでコードを書きがちなので…

Foreground Serviceを使うときは、タスクキルに要注意です。