diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index 8fe4167..2fc9b4c 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -469,8 +469,16 @@
     fn removeVmInstance(&self, instance_id: &[u8; 64]) -> binder::Result<()> {
         let state = &mut *self.state.lock().unwrap();
         if let Some(sk_state) = &mut state.sk_state {
-            info!("removeVmInstance(): delete secret");
-            sk_state.delete_ids(&[*instance_id]);
+            let uid = get_calling_uid();
+            info!(
+                "Removing a VM's instance_id: {:?}, for uid: {:?}",
+                hex::encode(instance_id),
+                uid
+            );
+
+            let user_id = multiuser_get_user_id(uid);
+            let app_id = multiuser_get_app_id(uid);
+            sk_state.delete_id(instance_id, user_id, app_id);
         } else {
             info!("ignoring removeVmInstance() as no ISecretkeeper");
         }
diff --git a/virtualizationservice/src/maintenance.rs b/virtualizationservice/src/maintenance.rs
index 4732e1f..8e04075 100644
--- a/virtualizationservice/src/maintenance.rs
+++ b/virtualizationservice/src/maintenance.rs
@@ -90,14 +90,15 @@
         self.get_inner()?.delete_ids_for_app(user_id, app_id)
     }
 
-    /// Delete the provided VM IDs from both Secretkeeper and the database.
-    pub fn delete_ids(&mut self, vm_ids: &[VmId]) {
+    /// Delete the provided VM ID associated with `(user_id, app_id)` from both Secretkeeper and
+    /// the database.
+    pub fn delete_id(&mut self, vm_id: &VmId, user_id: u32, app_id: u32) {
         let Ok(inner) = self.get_inner() else {
             warn!("No Secretkeeper available, not deleting secrets");
             return;
         };
 
-        inner.delete_ids(vm_ids)
+        inner.delete_id_for_app(vm_id, user_id, app_id)
     }
 
     /// Perform reconciliation to allow for possibly missed notifications of user or app removal.
@@ -157,6 +158,16 @@
         self.vm_id_db.add_vm_id(vm_id, user_id, app_id)
     }
 
+    fn delete_id_for_app(&mut self, vm_id: &VmId, user_id: u32, app_id: u32) {
+        if !self.vm_id_db.is_vm_id_for_app(vm_id, user_id, app_id).unwrap_or(false) {
+            info!(
+                "delete_id_for_app - VM id not associated with user_id={user_id}, app_id={app_id}"
+            );
+            return;
+        }
+        self.delete_ids(&[*vm_id])
+    }
+
     fn delete_ids_for_user(&mut self, user_id: i32) -> Result<()> {
         let vm_ids = self.vm_id_db.vm_ids_for_user(user_id)?;
         info!(
@@ -371,8 +382,8 @@
     #[test]
     fn test_sk_state_batching() {
         let history = Arc::new(Mutex::new(Vec::new()));
-        let mut sk_state = new_test_state(history.clone(), 2);
-        sk_state.delete_ids(&[VM_ID1, VM_ID2, VM_ID3, VM_ID4, VM_ID5]);
+        let sk_state = new_test_state(history.clone(), 2);
+        sk_state.inner.unwrap().delete_ids(&[VM_ID1, VM_ID2, VM_ID3, VM_ID4, VM_ID5]);
         let got = (*history.lock().unwrap()).clone();
         assert_eq!(
             got,
@@ -387,8 +398,8 @@
     #[test]
     fn test_sk_state_no_batching() {
         let history = Arc::new(Mutex::new(Vec::new()));
-        let mut sk_state = new_test_state(history.clone(), 6);
-        sk_state.delete_ids(&[VM_ID1, VM_ID2, VM_ID3, VM_ID4, VM_ID5]);
+        let sk_state = new_test_state(history.clone(), 6);
+        sk_state.inner.unwrap().delete_ids(&[VM_ID1, VM_ID2, VM_ID3, VM_ID4, VM_ID5]);
         let got = (*history.lock().unwrap()).clone();
         assert_eq!(got, vec![SkOp::DeleteIds(vec![VM_ID1, VM_ID2, VM_ID3, VM_ID4, VM_ID5])]);
     }
@@ -402,7 +413,7 @@
         get_db(&mut sk_state).add_vm_id(&VM_ID2, USER1, APP_A).unwrap();
         get_db(&mut sk_state).add_vm_id(&VM_ID3, USER2, APP_B).unwrap();
         get_db(&mut sk_state).add_vm_id(&VM_ID4, USER3, APP_A).unwrap();
-        get_db(&mut sk_state).add_vm_id(&VM_ID5, USER3, APP_C).unwrap(); // Overwrites APP_A
+        get_db(&mut sk_state).add_vm_id(&VM_ID5, USER3, APP_C).unwrap();
         assert_eq!((*history.lock().unwrap()).clone(), vec![]);
 
         sk_state.delete_ids_for_app(USER2, APP_B).unwrap();
@@ -425,6 +436,36 @@
     }
 
     #[test]
+    fn test_sk_state_delete_id() {
+        let history = Arc::new(Mutex::new(Vec::new()));
+        let mut sk_state = new_test_state(history.clone(), 2);
+
+        get_db(&mut sk_state).add_vm_id(&VM_ID1, USER1, APP_A).unwrap();
+        get_db(&mut sk_state).add_vm_id(&VM_ID2, USER1, APP_A).unwrap();
+        get_db(&mut sk_state).add_vm_id(&VM_ID3, USER2, APP_B).unwrap();
+        assert_eq!((*history.lock().unwrap()).clone(), vec![]);
+
+        // A VM ID that doesn't exist anywhere - no delete
+        sk_state.delete_id(&VM_ID4, USER1 as u32, APP_A as u32);
+        assert_eq!((*history.lock().unwrap()).clone(), vec![]);
+
+        // Wrong app ID - no delete
+        sk_state.delete_id(&VM_ID1, USER1 as u32, APP_B as u32);
+        assert_eq!((*history.lock().unwrap()).clone(), vec![]);
+
+        // Wrong user ID - no delete
+        sk_state.delete_id(&VM_ID1, USER2 as u32, APP_A as u32);
+        assert_eq!((*history.lock().unwrap()).clone(), vec![]);
+
+        // This porridge is just right.
+        sk_state.delete_id(&VM_ID1, USER1 as u32, APP_A as u32);
+        assert_eq!((*history.lock().unwrap()).clone(), vec![SkOp::DeleteIds(vec![VM_ID1])]);
+
+        assert_eq!(vec![VM_ID2], get_db(&mut sk_state).vm_ids_for_user(USER1).unwrap());
+        assert_eq!(vec![VM_ID3], get_db(&mut sk_state).vm_ids_for_user(USER2).unwrap());
+    }
+
+    #[test]
     fn test_sk_state_reconcile() {
         let history = Arc::new(Mutex::new(Vec::new()));
         let mut sk_state = new_test_state(history.clone(), 20);
diff --git a/virtualizationservice/src/maintenance/vmdb.rs b/virtualizationservice/src/maintenance/vmdb.rs
index 273f340..3519015 100644
--- a/virtualizationservice/src/maintenance/vmdb.rs
+++ b/virtualizationservice/src/maintenance/vmdb.rs
@@ -272,6 +272,21 @@
         Ok(vm_ids)
     }
 
+    /// Determine whether the specified VM ID is associated with `(user_id, app_id)`. Returns false
+    /// if there is no such VM ID, or it exists but is not associated.
+    pub fn is_vm_id_for_app(&mut self, vm_id: &VmId, user_id: u32, app_id: u32) -> Result<bool> {
+        let mut stmt = self
+            .conn
+            .prepare(
+                "SELECT COUNT(*) FROM main.vmids \
+                        WHERE vm_id = ? AND user_id = ? AND app_id = ?;",
+            )
+            .context("failed to prepare SELECT stmt")?;
+        stmt.query_row(params![vm_id, user_id, app_id], |row| row.get(0))
+            .context("query failed")
+            .map(|n: usize| n != 0)
+    }
+
     /// Determine the number of VM IDs associated with `(user_id, app_id)`.
     pub fn count_vm_ids_for_app(&mut self, user_id: i32, app_id: i32) -> Result<usize> {
         let mut stmt = self
@@ -350,6 +365,7 @@
     const VM_ID3: VmId = [3u8; 64];
     const VM_ID4: VmId = [4u8; 64];
     const VM_ID5: VmId = [5u8; 64];
+    const VM_ID_UNKNOWN: VmId = [6u8; 64];
     const USER1: i32 = 1;
     const USER2: i32 = 2;
     const USER3: i32 = 3;
@@ -506,6 +522,13 @@
         assert_eq!(empty, db.vm_ids_for_app(USER1, APP_UNKNOWN).unwrap());
         assert_eq!(0, db.count_vm_ids_for_app(USER1, APP_UNKNOWN).unwrap());
 
+        assert!(db.is_vm_id_for_app(&VM_ID1, USER1 as u32, APP_A as u32).unwrap());
+        assert!(!db.is_vm_id_for_app(&VM_ID1, USER2 as u32, APP_A as u32).unwrap());
+        assert!(!db.is_vm_id_for_app(&VM_ID1, USER1 as u32, APP_B as u32).unwrap());
+        assert!(!db.is_vm_id_for_app(&VM_ID_UNKNOWN, USER1 as u32, APP_A as u32).unwrap());
+        assert!(!db.is_vm_id_for_app(&VM_ID5, USER3 as u32, APP_A as u32).unwrap());
+        assert!(db.is_vm_id_for_app(&VM_ID5, USER3 as u32, APP_C as u32).unwrap());
+
         db.delete_vm_ids(&[VM_ID2, VM_ID3]).unwrap();
 
         assert_eq!(vec![VM_ID1], db.vm_ids_for_user(USER1).unwrap());