Updated: added pictures. Bumped the timestamp to make this post new again.
I don't know how I missed this, but apparently VirtualBox finally supports a "Scale Mode."
I've always wanted this feature. Why, you ask?
One easy example is for running an old operating system (older than Windows 2000) that isn't supported by VirtualBox, so that there are no Guest Additions for it. Guest Additions for supported OS's install extra drivers for the virtual machine, so that when you put VirtualBox into "Full Screen" mode, the guest OS will automatically increase its screen resolution to fit your display. When it can't do that, it will just display the screen at its literal resolution and put a black margin to fill in the extra space.
Here is an expertly Photoshopped demonstration of what I'm talking about. If you were running a Windows 3.1 virtual machine at an 800x600 screen resolution, and you put the VM full-screen, this is what it would look like on your 1366x768 monitor:
Another example: even on supported guests, running an older game like Starcraft (which runs in a resolution of 640x480) had this problem too: if the VM is running Full Screen and you start Starcraft... instead of the game's display stretching across your whole monitor, it stays at 640x480 pixels and is centered on the screen. This sucks.
So it seems VirtualBox has finally added Scale Mode (available in the "Machine" menu along side Full Screen and Seamless modes). There's one quirk to it, though: Scale Mode and Full Screen don't work together. On my system, going into Scale Mode put the virtual machine into a window on my screen. This window could be maximized, but it couldn't be made full screen. So that sorta sucks.
Luckily, my Linux window manager (xfwm4, the window manager of the XFCE desktop environment) supports putting any window full screen, whether the window wants it or not. This means the window decorations are taken away and the contents of the window are resized to fill the display. Success! I can now run full screen, scaled resolution guest operating systems.
Scale mode with xfwm4's full-screen option gives you a "native" experience.