Ended up without virtual hard disk space on my Windows XP machine. Never thought I’d need more than 10GB. Luckily, starting with VirtualBox version 4.0, you can resize your virtual hard disks with:
vboxmanage modifyhd DiskName.vdi --resize 15000
where DiskName.vdi is your disks name, and the resize value is in megabytes. I have tested this with .vdi disks (default VirtualBox disk format), no idea if it works for other types of disks.
After this, you should extend the partition itself. I guess booting GParted would be the easiest way if you’re running Win XP.