Android имеет своего рода кеш, который отслеживает медиа-файлы.
Попробуйте это:
sendBroadcast(new Intent(Intent.ACTION_MEDIA_MOUNTED, Uri.parse("file://" + Environment.getExternalStorageDirectory())));
Он снова запускает службу MediaScanner, которая должна удалить удаленную песню из кэша устройства.
Вам также необходимо добавить это разрешение в свой AndroidManifest.xml:
<intent-filter>
<action android:name="android.intent.action.MEDIA_MOUNTED" />
<data android:scheme="file" />
</intent-filter>