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.

_________________
Luke
Recovery Force Data Recovery

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.

_________________
• Remote RAID, NAS, SAN, VMware, DVR (CCTV), flash and tape recovery. Data recovery support.