Colin Watson asked that I discuss this issue in #ubuntu-kernel. A log of the IRC discussion is below, as requested by Martin Pitt, and I'll attach a debdiff for 'grub-gfxpayload-lists' in due course:

 Here is what we discussed:

<flexiondotorg> I been discussing https://bugs.launchpad.net/ubuntu/+source/virtualbox/+bug/1368784/ with cjwatson in #ubuntu-devel
<ubot5> Ubuntu bug 1368784 in virtualbox (Ubuntu) "Vivid and Utopic Virtualbox guest gets only up to resolution of 640x480" [High,Confirmed]
<flexiondotorg> I've got the following work around - https://bugs.launchpad.net/ubuntu/+source/virtualbox/+bug/1368784/comments/17
<flexiondotorg> cjwatson is prepared to update grub-gfxpayload-lists if someone here can confirm "fixing" this issue at a kernel level is hopeless.
<flexiondotorg> So, thoughts?
<apw> flexiondotorg, "fixing" at the kernel level, do we know what the issue is ?
<apw> flexiondotorg, the implication of the (admittedly older) comments is that you need virtualbox-guest-x11
<apw> flexiondotorg, and indeed i can confirm that installing the said package does sort things out, who knows what i has in it mind
<apw> seems it has a vbox specific video drivers
<apw> i wonder if they should be being installed by jockey
<flexiondotorg> apw, So the issue is the default resolution when virtualbox-guest-x11 is not installed.
<apw> the default resolution is that offered by the vesa settings i assume ?
<flexiondotorg> apw, The vmware video devices are already blacklisted by grub-gfxpayload-lists
<apw> ok, so then it sounds like whatever this is using now is a candidate for blacklisting ?
<flexiondotorg> apw, Must be. vesa is used by vbox when the guestadditions-x11 is absent.
<apw> so that is a vbox issue really, offering stupid resolutions by default
<flexiondotorg> apw, Since 14.04. Yes.
<flexiondotorg> apw, The 640x480 thing started sometime during 14.10.
<apw> and presumably it does that because they don't care about you if you don't install their video driver
<flexiondotorg> apw, I couldn't possibly comment ;)
<apw> i wonder why i makes a difference to blacklist it in grub though, vesa must be very broken
<apw> and so i would think rather than being a fallback option to blacklist more things in grub, it might
<apw> be the appropriate option instead
<flexiondotorg> apw, It is odd because when booting from the live media, resolution is 1024x768.
<flexiondotorg> But on first install, resolution is 640x480.
<apw> right, that doesn't use grub, nor initialise the display
<apw> it uses syslinux
<flexiondotorg> apw, Indeed.
<apw> grub initialises the display, because you know the vesa modes offered should be the preferred size of your display, so setting it up early makes sense and makes things prettier
<apw> unless your vesa config is spam
<apw> and has "1 1024x768 2 640x480 (default)" in it ... or equiv
<flexiondotorg> So, possibly a regression in what Virtualbox provides.
<apw> but if we are blacklisting for vbox video anyhow, it may well make sense to blacklist everything when vbox is found
<apw> which is what i assume the wildcard you added does
<flexiondotorg> apw, Yes.
<flexiondotorg> Although, AKAIK, vbox have only ever used one device ID for video.
<apw> flexiondotorg, not that i really know why one would use vbox if you had any other choice
<flexiondotorg> The other "work around" is to configure grub to use 'console' for all video output.
<flexiondotorg> apw, It is very popular with people who just want to test. Low barrier of entry.
<apw> flexiondotorg, i don't find virtmgr any more complex to drive, and it idoesn't have these issue at least
<flexiondotorg> apw, Agreed.
<apw> and i don't need 30k lines of random out of tree junk loaded into my kernle to make it work either
<flexiondotorg> But, people do use vbox.
<flexiondotorg> apw, So the question is. Is this fixable by the kernel team? Seems like a big fat "No" based on what we've discussed?
<apw> well they had much more ufn, they were just exploding in the host when they tried
<apw> flexiondotorg, i am not sure what we would fix, grub handed us a configured terminal, and we continued to use it as instructed
<apw> flexiondotorg, and presumably because vesa, it was at a stupid resolution
<apw> i'll try your workaround on that same gnome image in vbox and see how it looks
<flexiondotorg> apw, So I think that blacklisting the vbox video device in grub is the way forward.
<flexiondotorg> apw, OK. Thanks for testing.
<apw> flexiondotorg, and i think the behaviour with the blacklist seems more useful, and i assume if i install the -guest-x11 i'll get go faster stripes
<flexiondotorg> apw, Yes with guest-x11 install you get dynamic resizing and such.
<apw> flexiondotorg, but yes, i htink my prefrered option is this blacklist, and if it fixes the issues you have with locked disks that sounds liek a win
<flexiondotorg> apw, Agreed. Although the inability to enter encryption pass phrases affects actual hardware too. By blacklisting vbox for grub you get a text mode plymouth which always works.
<apw> flexiondotorg, yeah, i assume we have a lot of issues there now we have systemd fun to play with
<apw> i guess i ought to reinstall some of my kit with that to find out
<flexiondotorg> apw, systemd isn't to blame for passphrase entry. That was present in 14.10 also.
<flexiondotorg> apw, My "solution" was not to ship a graphical plymouth theme in 14.10. That way only text mode available and pass phrase entry worked.
<flexiondotorg> apw, Are you still testing this on an Ubuntu GNOME image or have we concluded that blacklisting is the solution?
<apw> i think we concur blacklisting is the way forward for the size issue
<apw> the plymouth not working is separate
<flexiondotorg> apw, Thanks for your time.
<apw> flexiondotorg, thanks for paying attention to it :)
<flexiondotorg> apw, I'll report back to cjwatson and he can make the blacklist change.
<flexiondotorg> apw, Most welcome :)
<apw> ack, thanks