Finally got a decent answer at the VBox forums thread that points me to this solution. It seems it is a problem with the framebuffer. Will try this later tonight or tomorrow and post results.
Sounded promising, but couldn't make it work. Also the latest version of ubuntu introduces Grub2 which removes menu.lst. I believe all I need to perform step 6 is to edit /etc/default/grub instead. And I did. To be sure I also boot-shift and edited the menu entry to include the vga line. But to no avail.
No dice and I gave up on it. Back to my beloved Arch. Will keep VirtualBox though. This doesn't seem to me anymore an issue with VBox.
So I heard :p
But that is precisely my problem. I'm a passable linux user at best. Interested, yes. But not willing to dig too far. So my incompetence shows: For instance, while I was aware that VBoxManager setextradata would have no influence on the console, I failed to realize something more basic: that GRUB_GFXMODE only affects the grub loader (duh!). There's one thing more dangerous than letting someone who doesn't know a thing work around your machine; letting someone clueless work around your machine
Anyways, there's been some developments on the VirtualBox forum. Setting the bit depth to 8 bits suddenly makes it work! Hurrah! So I think I'm ready to setup Arch on a VBox VM.