VirtualBox disk image (VDI) file size grows proportionally to space used by guest OS, however the space occupied by the image is not reclaimed when you delete files inside it.

Deleting files generally removes reference to data from directory structure, but the data still exists on disk. It is considered as free block which will be "overwritten" by contents of newly created files. VirtualBox software gives ability to compact VDI images by removing such unused disk blocks, but they need to be zeroed first. This can be achieved by tool called zerofill available on Ubuntu (I tested with 10.04 LTS).

Make backup of you image before you follow instructions below.

Run these operations on guest OS:

  1. Install zerofile: sudo apt-get install
  2. Reboot OS and keep Shift key pressed until you boot to GRUB menu.
  3. Select default kernel but with Recovery option, do not confim, just press x key. You will enter boot options menu.
  4. Now just append " init=/bin/bash" to linux line (it may be wrapped!). This trick helps booting to single user mode and mount root disk read-only. Continue boot by pressing Ctrl+X.
  5. Once you reach bash prompt, run:
    mount -n -o remount,ro /dev/sda1 /
  6. Now you can clean successfully mounted disk:
    zerofill /dev/sda1
  7. Stop OS with shutdown -h now eventually exit and shut down guest manually from VirtualBox.

Now close VirtualBox on host OS and run command:
VBoxManage modifyhd PathTo/YourUbuntuImage.vdi --compact

Now, depending on guest OS usage, the result will be considerable smaller VDI image file.