diff --git a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
index 4ffef3c..12a46f7 100644
--- a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
+++ b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
@@ -2107,12 +2107,9 @@
         IVmShareTestService service = connection.waitForService();
         assertWithMessage("Timed out connecting to " + serviceIntent).that(service).isNotNull();
 
+
         try {
-            // Send the VM descriptor to the other app. When received, it will reconstruct the VM
-            // from the descriptor, start it, connect to the ITestService in it, creates a "proxy"
-            // ITestService binder that delegates all the calls to the VM, and share it with this
-            // app. It will allow us to verify assertions on the running VM in the other app.
-            ITestService testServiceProxy = service.startVm(vmDesc);
+            ITestService testServiceProxy = transferAndStartVm(service, vmDesc, "vm_to_share");
 
             int result = testServiceProxy.addInteger(37, 73);
             assertThat(result).isEqualTo(110);
@@ -2163,12 +2160,7 @@
         assertWithMessage("Timed out connecting to " + serviceIntent).that(service).isNotNull();
 
         try {
-            // Send the VM descriptor to the other app. When received, it will reconstruct the VM
-            // from the descriptor, start it, connect to the ITestService in it, creates a "proxy"
-            // ITestService binder that delegates all the calls to the VM, and share it with this
-            // app. It will allow us to verify assertions on the running VM in the other app.
-            ITestService testServiceProxy = service.startVm(vmDesc);
-
+            ITestService testServiceProxy = transferAndStartVm(service, vmDesc, "vm_to_share");
             String result = testServiceProxy.readFromFile("/mnt/encryptedstore/private.key");
             assertThat(result).isEqualTo(EXAMPLE_STRING);
         } finally {
@@ -2176,6 +2168,25 @@
         }
     }
 
+    private ITestService transferAndStartVm(
+            IVmShareTestService service, VirtualMachineDescriptor vmDesc, String vmName)
+            throws Exception {
+        // Send the VM descriptor to the other app. When received, it will reconstruct the VM
+        // from the descriptor.
+        service.importVm(vmDesc);
+
+        // Now that the VM has been imported, we should be free to delete our copy (this is
+        // what we recommend for VM transfer).
+        getVirtualMachineManager().delete(vmName);
+
+        // Ask the other app to start the imported VM, connect to the ITestService in it, create
+        // a "proxy" ITestService binder that delegates all the calls to the VM, and share it
+        // with this app. It will allow us to verify assertions on the running VM in the other
+        // app.
+        ITestService testServiceProxy = service.startVm();
+        return testServiceProxy;
+    }
+
     @Test
     @CddTest(requirements = {"9.17/C-1-5"})
     public void testFileUnderBinHasExecutePermission() throws Exception {
diff --git a/tests/vmshareapp/aidl/com/android/microdroid/test/vmshare/IVmShareTestService.aidl b/tests/vmshareapp/aidl/com/android/microdroid/test/vmshare/IVmShareTestService.aidl
index fe6ca43..ac59610 100644
--- a/tests/vmshareapp/aidl/com/android/microdroid/test/vmshare/IVmShareTestService.aidl
+++ b/tests/vmshareapp/aidl/com/android/microdroid/test/vmshare/IVmShareTestService.aidl
@@ -20,5 +20,7 @@
 
 /** {@hide} */
 interface IVmShareTestService {
-    ITestService startVm(in VirtualMachineDescriptor vmDesc);
+    void importVm(in VirtualMachineDescriptor vmDesc);
+
+    ITestService startVm();
 }
diff --git a/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java b/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
index dc8908b..109486c 100644
--- a/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
+++ b/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
@@ -93,16 +93,19 @@
         }
     }
 
-    public ITestService startVm(VirtualMachineDescriptor vmDesc) throws Exception {
+    public void importVm(VirtualMachineDescriptor vmDesc) throws Exception {
         // Cleanup VM left from the previous test.
         deleteVm();
 
-        VirtualMachineManager vmm = getSystemService(VirtualMachineManager.class);
-
         // Add random uuid to make sure that different tests that bind to this service don't trip
         // over each other.
         String vmName = "imported_vm" + UUID.randomUUID();
 
+        VirtualMachineManager vmm = getSystemService(VirtualMachineManager.class);
+        mVirtualMachine = vmm.importFromDescriptor(vmName, vmDesc);
+    }
+
+    public ITestService startVm() throws Exception {
         final CountDownLatch latch = new CountDownLatch(1);
         VirtualMachineCallback callback =
                 new VirtualMachineCallback() {
@@ -134,10 +137,9 @@
                     }
                 };
 
-        mVirtualMachine = vmm.importFromDescriptor(vmName, vmDesc);
         mVirtualMachine.setCallback(getMainExecutor(), callback);
 
-        Log.i(TAG, "Starting VM " + vmName);
+        Log.i(TAG, "Starting VM " + mVirtualMachine.getName());
         mVirtualMachine.run();
         if (!latch.await(1, TimeUnit.MINUTES)) {
             throw new TimeoutException("Timed out starting VM");
@@ -155,10 +157,21 @@
     final class ServiceImpl extends IVmShareTestService.Stub {
 
         @Override
-        public ITestService startVm(VirtualMachineDescriptor vmDesc) {
+        public void importVm(VirtualMachineDescriptor vmDesc) {
+            Log.i(TAG, "importVm binder call received");
+            try {
+                VmShareServiceImpl.this.importVm(vmDesc);
+            } catch (Exception e) {
+                Log.e(TAG, "Failed to importVm", e);
+                throw new IllegalStateException("Failed to importVm", e);
+            }
+        }
+
+        @Override
+        public ITestService startVm() {
             Log.i(TAG, "startVm binder call received");
             try {
-                return VmShareServiceImpl.this.startVm(vmDesc);
+                return VmShareServiceImpl.this.startVm();
             } catch (Exception e) {
                 Log.e(TAG, "Failed to startVm", e);
                 throw new IllegalStateException("Failed to startVm", e);
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());