How do I delete a VM in VirtualBox when the hard drive the VDI file was on is deleted?

Delete your VM xml files on Hard Disk. They are located by default in C:\Users\YOUR_NAME\.VirtualBox\Machines.

After deleting, you'll still receive strange erros messages in Virtualbox. This is because some info about your vms are inside C:\Users\YOUR_NAME\.VirtualBox\VirtualBox.xml.

If you don't mind losing some global configuration in your VirtualBox, just delete this file. Virtualbox will create another if it doesn't exist.

If you just want to remove a specific VM, you have to edit Virtualbox.xml in some xml editor (notepad is fine. notepad++ is better since it has syntax highlighting).

You'll find these fields:

<MachineRegistry>
  <MachineEntry uuid="UUID" src="Machines\MACHINE_NAME\MACHINE_NAME.xml"/>
</MachineRegistry>
<MediaRegistry>
  <HardDisks>
    <HardDisk uuid="UUID" location="HardDisks\DISC_NAME.vdi" format="VDI" type="Normal"/>
  </HardDisks>
  <DVDImages>
    <Image uuid="UUID" location="C:\IMAGES\IMAGE.iso"/>
  </DVDImages>
  <FloppyImages/>
</MediaRegistry>

Remove the MachineEntry from the desired VM. If you just have one VM and want to remove everything, just leave the tags empty. For example:

<MachineRegistry/>
<MediaRegistry>
  <HardDisks/>
  <DVDImages/>
  <FloppyImages/>
</MediaRegistry>

...and you're done. I just tested everythong here and it works flawlessly. If you want to avoid problems, backup your xml configuration files from VirtualBox and specific VMs.

(I didn't mention about snapshots, but I believe it's the same principle.)

Instructions above did not solve the issue for me. I wanted to remove a specific machine, not all of them. I did not have a MachineEntry for the specific machine in this file anymore: C:\Users\YOUR_NAME\.VirtualBox\VirtualBox.xml

However, machine was still showing up in the Virtual Media Manager, and I was not able to remove it from here.

Restarting VirtualBox did not work either.

What worked: Restarting VBoxSVC.exe process and then restarting VirtuaBbox.

First, delete any snapshots of that Virtual Machine. Then open the settings of the Virtual Machine, go to Storage tab, right click on the vdi file under IDE Controller and click on Remove Attachment. Now you should be able to remove the VDI from the Virtual Media Manager.