Escrever zeros no espaço livre não é difícil (mesmo no Windows!). Basta escrever um arquivo contendo zeros, até ficar sem espaço. No unix, é um simples comando shell:
cat /dev/zero >fill_er_up
rm fill_er_up
Eu vi instruções para reduzir a imagem .vdi para uma máquina guest do Windows no VirtualBox 4.1.8. No entanto, usou uma ferramenta para escrever zeros para liberar espaço no arquivo .vdi (nullfile-1.02.exe) que é somente para Windows.
A página disse que você deveria encontrar um zerospace.c para fazê-lo em um guest Linux, mas não consigo encontrar um arquivo desse tipo em qualquer lugar da Internet.
Alguém aqui tem experiência em diminuir os convidados do VirtualBox Linux?