diff --git a/javalib/src/android/system/virtualmachine/VirtualMachine.java b/javalib/src/android/system/virtualmachine/VirtualMachine.java
index db5b4d1..b040cc0 100644
--- a/javalib/src/android/system/virtualmachine/VirtualMachine.java
+++ b/javalib/src/android/system/virtualmachine/VirtualMachine.java
@@ -311,6 +311,9 @@
     @Nullable
     private ParcelFileDescriptor mLogWriter;
 
+    @GuardedBy("mLock")
+    private boolean mWasDeleted = false;
+
     /** The registered callback */
     @GuardedBy("mCallbackLock")
     @Nullable
@@ -506,6 +509,9 @@
     void delete(Context context, String name) throws VirtualMachineException {
         synchronized (mLock) {
             checkStopped();
+            // Once we explicitly delete a VM it must remain permanently in the deleted state;
+            // if a new VM is created with the same name (and files) that's unrelated.
+            mWasDeleted = true;
             deleteVmDirectory(context, name);
         }
     }
@@ -587,6 +593,9 @@
     public int getStatus() {
         IVirtualMachine virtualMachine;
         synchronized (mLock) {
+            if (mWasDeleted) {
+                return STATUS_DELETED;
+            }
             virtualMachine = mVirtualMachine;
         }
         if (virtualMachine == null) {
@@ -617,7 +626,7 @@
     // Throw an appropriate exception if we have a running VM, or the VM has been deleted.
     @GuardedBy("mLock")
     private void checkStopped() throws VirtualMachineException {
-        if (!mVmRootPath.exists()) {
+        if (mWasDeleted || !mVmRootPath.exists()) {
             throw new VirtualMachineException("VM has been deleted");
         }
         if (mVirtualMachine == null) {
@@ -653,7 +662,7 @@
                     && stateToStatus(mVirtualMachine.getState()) == STATUS_RUNNING) {
                 return mVirtualMachine;
             } else {
-                if (!mVmRootPath.exists()) {
+                if (mWasDeleted || !mVmRootPath.exists()) {
                     throw new VirtualMachineException("VM has been deleted");
                 } else {
                     throw new VirtualMachineException("VM is not in running state");
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 f3bbbf1..160b679 100644
--- a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
+++ b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
@@ -429,31 +429,37 @@
         VirtualMachineManager vmm = getVirtualMachineManager();
         String vmName = "vmName";
 
-        // VM does not yet exist
-        assertThat(vmm.get(vmName)).isNull();
+        try {
+            // VM does not yet exist
+            assertThat(vmm.get(vmName)).isNull();
 
-        VirtualMachine vm1 = vmm.create(vmName, config);
+            VirtualMachine vm1 = vmm.create(vmName, config);
 
-        // Now it does, and we should get the same instance back
-        assertThat(vmm.get(vmName)).isSameInstanceAs(vm1);
-        assertThat(vmm.getOrCreate(vmName, config)).isSameInstanceAs(vm1);
+            // Now it does, and we should get the same instance back
+            assertThat(vmm.get(vmName)).isSameInstanceAs(vm1);
+            assertThat(vmm.getOrCreate(vmName, config)).isSameInstanceAs(vm1);
 
-        // Can't recreate it though
-        assertThrowsVmException(() -> vmm.create(vmName, config));
+            // Can't recreate it though
+            assertThrowsVmException(() -> vmm.create(vmName, config));
 
-        vmm.delete(vmName);
-        assertThat(vmm.get(vmName)).isNull();
+            vmm.delete(vmName);
+            assertThat(vmm.get(vmName)).isNull();
 
-        // Now that we deleted the old one, this should create rather than get, and it should be a
-        // new instance.
-        VirtualMachine vm2 = vmm.getOrCreate(vmName, config);
-        assertThat(vm2).isNotSameInstanceAs(vm1);
+            // Now that we deleted the old one, this should create rather than get, and it should be
+            // a new instance.
+            VirtualMachine vm2 = vmm.getOrCreate(vmName, config);
+            assertThat(vm2).isNotSameInstanceAs(vm1);
 
-        // Subsequent gets should return this new one.
-        assertThat(vmm.get(vmName)).isSameInstanceAs(vm2);
-        assertThat(vmm.getOrCreate(vmName, config)).isSameInstanceAs(vm2);
+            // The old one must remain deleted, or we'd have two VirtualMachine instances referring
+            // to the same VM.
+            assertThat(vm1.getStatus()).isEqualTo(STATUS_DELETED);
 
-        vmm.delete(vmName);
+            // Subsequent gets should return this new one.
+            assertThat(vmm.get(vmName)).isSameInstanceAs(vm2);
+            assertThat(vmm.getOrCreate(vmName, config)).isSameInstanceAs(vm2);
+        } finally {
+            vmm.delete(vmName);
+        }
     }
 
     @Test