I'm trying to reduce the size of a Linux virtual image that I want to use as a base image for further work. Initially I picked a 16 GB dynamically expanding disk. Then I installed Ubuntu server with the packages I need. Disk size: ~500MB. Then I upgraded all packages to the latest version. Disk size in the guest OS: ~520MB. Disk size of the .vdi virtual image: more than 1GB! Compacting the .vdi doesn't reduce its size.

What I need is a tool to clean up the unused disk space and fill it with zeros so that VirtualBox can compact the .vdi file back to 520MB.

There's a lot of documentation out there on how to do this for Windows (delete unnecessary files with CCleaner, defrag and then fill the free space with zeros using some tool called sdelete.exe)

I've found several links suggesting that creating a huge file full of zeros would do the trick (e.g. dd if=/dev/zero of=~/zeros) but that only increased the size of the .vdi image in the end.

I guess it's a problem with the ext3 file system that Ubuntu uses. I don't know much about it, but a large file doesn't work...

So far the only way to handle it was to create a new virtual hard disk, copy the whole installation over and fix the bootloader. That's hardly practical to do... Isn't there some better way?

try using the reiserfs filesystem. it can handle small files very well.
maybe that will help.
but i'm not sure about that huge file with zeros. although it will fill the image with many zeros, the filesystem will have to create a lot of metadata to go with those zeros(i think).

Seems it's been removed - do you get the "Error: Shrink hard disk operation is not implemented! " message ?.
Open ticket here

Yes, the "shrink" feature in VirtualBox is gone since version 2.1 or so. But you can still do it with the "clonehd" command, which creates a shrinked version.

I've tried the ReiserFS briefly, and on a freshly created .vdi it seems to work!!!! Thanks for the tip!