HDD GURU FORUMS

Unintentionally I deleted my .vdi file (VirtualBox), but I recovered the file using Recuva, the vdi has a Windows 7 x64 guest with 120 GB, and I recovered to the same Hard Drive (The HD was 500 GB free space and it wasn't the boot HD) now I can't start the virtual machine and VirtualBox says:

Failed to open the disk image file X:\My virtual machine.vdi.

Could not get the storage format of the medium 'X:\My virtual machine.vdi.' (VERR_NOT_SUPPORTED).

Result code: VBOX_E_IPRT_ERROR (0x80BB0005)
Component: MediumWrap
Interface: IMedium {4afe423b-43e0-e9d0-82e8-ceb307940dda}
Caller: IVirtualBox {0169423f-46b4-cde9-91af-1e9d5b6cd945}
RC Caller: VBOX_E_OBJECT_NOT_FOUND (0x80BB0001)

How can I recover my files from the VDI?

You likely corrupted the sectors of the file by writing over it with your recovery. That damage cannot be undone. Sorry.

Recovering to the same drive and with Recuva was a bad idea indeed.

I haven't heard about any software, which would allow to open a VirtualBox Disk and recover data automatically.

Try the following:
Create a new, guest virtual box with the same OS, start it and then try to attach your damaged virtual disk as a second drive on that new machine.

As a "level B" approach you can attempt mounting VDI file as a loop device in Linux, but to do so you'll need to analyze it manually and locate the MBR first.