Simply running 'VBoxManage modifyvd <your image.vdi> compact' didn't shrink the image, however the following that I found did:
Now my .vdi file is only 237MB.1. I can confirm that the 'dd if=/dev/zero of=/zerofile; rm /zerofile' does NOT allow to recover (all) unused space
2. Using the 'sfill -z /' utility from the 'secure-delete' (Debian/Ubuntu) package does NOT help either
A WORKING (quick and dirty) solution is:
3.a Boot using a GParted LiveCD
3.b Downsize existing partition(s) to the strict minimum
3.b Create temporary unformatted partition(s) in the unused disk space
3.d Fill the temporary unformatted partition(s) with zeroes, using 'dd if=/dev/zero of=/dev/...'
(and optionally do the same for the swap partition)
3.e Remove the temporary unformatted partition(s)
3.f Grow the partition(s) previously downsized in 3.b back to their original size
3.g Shutdown GParted
3.h Compact VDI image with 'VBoxManage modifyvdi ...'
I've actually used Parted Magic 4.4 to downsize the partition and created an unformatted partition with it too. The dd command took a while (22MB/s) to fill the 5GB unformatted partition.
Once you're done with the whole GParted phase, you need to run 'VBoxManage modify <your .vdi image> compact' to shrink the image!
Hope this can be helpful for someone