I'm afraid to say that we were discussing use of VirtualBox over VNC last week and decided that we can not afford to officially support it, precisely because keyboard over VNC is so hard to get working. PC virtualisation places higher requirements on keyboard support than most applications, which VNC servers generally do not handle in a way which is usable for us. It might be worth talking to the Vino developers to see what they think. If you do, I wrote up a bit of information on the wiki<1> a bit of information about VirtualBox keyboard handling which should help them to understand what is happening.
<1> https://www.virtualbox.org/wiki/X11Keyboard
The easiest solution might be for Vino to optionally send key codes matching those that X.Org uses. For this it would probably need to be told what layout was in use on the remote system. If the developers feel really adventurous, they can look at our legacy keyboard code which can detect the layout in use, though it is sadly not capable enough to detect it though a VNC connection.
