O truque é preencher o espaço não utilizado com zeros, depois pedir ao VB para encolher o disco.
Por exemplo: como root no Linux:
dd if=/dev/zero bs=1024k of=/bigfile; rm -f /bigfile
Em seguida, desligue a máquina e execute:
VBoxManage modifyhd diskfile.vdi --compact
Com a maior parte do disco cheio de zero, ele deve diminuir para algo próximo a 4 GB.