It is not possible to increase the maximum virtual size of a VirtualBox VDI HDD once it is created. The only way I found to do it is to create a new larger VirtualBox HDD and use GParted to copy the old one to the new one. The steps to do that are:
1. Create a new VirtualBox HDD with the desired size and add it as a secondary HDD (Primary Slave) in the Virtual Machine HDD settings.
2. Download the GParted LiveCD and boot from it inside the Guest – http://gparted.sourceforge.net/
3. Right click on the partitions of the original HDD in GParted and click “Copy“. Select the second HDD and “Paste”. This will ask to create a “msdos” partition table first so click “OK” and “Paste” again. Adjust partition sizes as you wish and hit “Apply“.
4. Mark the new partition as bootable in right click -> “Manage Flags” -> tick “boot“. Once done shutdown the VM and release the gparted Live CD.
5. Because the HDD characteristics have changed you might not be able to boot at this point. Insert the Windows/Linux OS installation CD/DVD and run in repair mode. For Windows this would be the recovery console and the “fixboot c:” or fixmbr commands. On Linux just reinstall the boot loader.
That’s it. It’s not very convenient doing this but at least it works.
P.S: If you get an error “FATAL: INT18 Boot Failure” you have forgotten to mark the new partition as bootable.