I have had the same issues. Installed latest guest addition and vbox ( 3.1.8 ). They do not solve the problems. Removing hardware acceleration will slow the video to a choppy speed on my pc which renders the full screen mode useless as far as I am concerned.
I would not hold my breath waiting for Sun to fix this bug (or any bugs in VBox - this thread was started in Dec 2008 and we're May 2010 as I write this reply). That's why I have figured out this little work around. It's a little ghetto and a little inconvenient but you won`t care if you want to watch a video in vbox badly enough (ex. if you don't trust the websites but want to watch certain types of videos or are running a proxy service to watch Hulu that installs software you don't trust etc etc)....
You need to find the maximum zoom that would (in Firefox's full screen mode) allow you to see the video without loosing any of the image and the control bar (the line under the video that allow you to fast forward and set the volume). This varies depending on your monitor resolution and proportion. In my case, I found that for my 16:9 and 1920x1080 monitor, 280% for youtube (with some scrolling), 215% for another video website were good. I like my minimum zoom at 150%. The inbuilt firefox zoom function wont allow you to be so precise. You need an extension from Mozilla Addons called Glazoom. Glazoom will allow you to key in the percentage of zoom you want. Once youve figure out the percentages you need, you can go to Glazoom's options menu and set exactly what percentages popup in the Glazoom menu in the status bar. For my zooms of 280%, 215% and 150% zoom percentages, I keyed in the options dialog: 2.8, 2.15 and 1.5 (zoom percentage divided by a hundred). You can also set the minimum zoom in the options menu, which I set to 150%. Unfortunately you cannot access the Glazoom menu from full screen as it is in the status bar, so you have to zoom to the level you want and then hit F11 and pan the video to the right position but this is still an improvement over Firefox`s native zoom functionality. When you're done with the video, hit F11 and select 150% (or whatever you set your minimum zoom at at) or go to another page and it will automatically revert to your minimum zoom.
This will allow you to see something very close to full screen flash without having to stop hardware acceleration (ie no choppiness).
If some website put annoying adds next to the video, use Adblock Plus to get rid of the frame. If you use personas and the little sliver of color that sticks around in full screen mode is bothering you, choose a black or dark persona. If you find the scroll bars destracting, change their colors to black and dark grey.
It's a little bit of a pain to setup but it works and becomes automatic once you have it setup.