If you are using snapshots, this isn’t an easy feat. You need to reconstruct the snapshot tree, with only a bunch of UUIDs to go on. Fortunately, each (differential) VDI file stores the UUID of it’s parent VDI. The following Python script parses a set of VDI files and tries to rebuild the tree:

http://github.com/miracle2k/linuxutils/blob/master/reconstruct-vdi-tree.py

It can output the XML code that goes into VirtualBox.xml directly. If your VM’s configuration file is also gone, the easiest way to go about seems to be:

• Create a new machine with your base VDI.
• Create snapshots matching the tree given by this script.
• Edit the VM-specific XML file, and VirtualBox.xml, changing the UUIDs of the dummy snapshots with the UUIDs given to you by this script.