How to compress a Virtual Box virtual hard disk file (VDI file)

1. Windows: defragment your guest drive

If on Windows, first defrag the guest virtual drive:
defrag C: -v -f

(on Linux, no need to defragment your drives!)

2. Zero out your free space

if the guest is Windows, use SysInternals tool 'sdelete':
sdelete -c C:\

if the guest is Linux, use the tool 'zerofree':
mount -n -o remount,ro -t ext2 /dev/sda1 /
mount -n -o remount,ro -t ext2 /dev/sdb1 /var
zerofree /dev/sda1
zerofree /dev/sdb1

3. Schedule a boot-time file system check. 
On Windows:
chkdsk C: /X /R /V


4. Reboot your VM
After the disk check completes, you can shutdown your VM.

5. On the host machine, you can then execute VBoxManage:

VBoxManage modifyvdi xxxx.vdi compact
where xxxx.vdi is the name of your VDI file.