VirtualBox harddrive file (.vdi) seems never shrink, whatever I do in the guest windows. We can fix this. Following is taken from http://kakku.wordpress.com.
For the reference, disk space can be also managed by turning off indexing, logging, restoring, and virtual memory. Also windows have a one stop cleaning center, which can be accessed by right clicking on the disk drive in the explorer.exe.

We’ll need the following tools:
1. http://www.feyrer.de/g4u/nullfile-1.02.exe : This tool zeroes out free space, which our next tool compresses. For Linux based OS, search for a file, zerospace.c, which you’ll have to compile yourself.
2. VBoxManage : This tool is the command line management tool that ships with VirtualBox. Whatever you can do with the GUI, can be done by this. + A lot more

Ok now.

1. First boot into your VM. Defragment your drive atleast 2 times.
2. Copy the tool, nullfile mentioned above to the VM and run it. A simple double click should do it.
3. Now shutdown the guest. Open a terminal in the VM image directory. Most probably /home/_user_name_/.VirtualBox/VDI
4. Run our final command, We would be done after this.
VBoxManage modifyvdi _file_path_ compact
e.g. in my case I ran: VBoxManage modifyvdi /media/Blockk/VDI/NewHardDisk1.vdi compact