ms_meme,
The problem is rare, but it's inherent in dual-booting two or more OSes. Any OS will set up the hardware the way it likes it and expect it to be in the state it set it to when it last shut down, or the default state set by the BIOS. A warm boot from another OS means it will be in the state the other OS left it in... This might mean the OS can't access it properly.
I would guess, judging by the Synaptic history and the symptoms, that the graphics card is likely to be the hardware in question, especially if it's nVidia. As someone else suggested, upgrading the driver in Windows to the latest version might help. Also, trying to adjust things on shutdown might help. As as suggested, you could try adding reboot=cold to your kernel line in /boot/grub/menu.lst and see what happens. Finding out what to add in /etc/rc6.d/ would be quite difficult unless a solution is already known.
However, there can be no guarantee one OS will leave hardware in a state that suits another, and the surprising thing is that this isn't a more common problem. Both Oses are actually working correctly, in that they can start everything when it is set up by the BIOS. No OS is designed to start hardware that has been left in an unpredictable state by another. If you have insufficient RAM to run Virtualbox you might just have to accept the inconvenience.