Current Firefox 3.6 pre-beta 1 nightlies now feature a full screen option for videos embedded using the <video> tag like the natively supported Theora encoders.
Just right click on the video and select Full Screen. While on full screen, press Escto return to the normal view.
There’s still a half second pause while switching modes that should be ironed in the next days, but is far better than the current Full Screen extension which forced a full video restart when switching modes. Neat!