Click left hand icon to set fullscreen, then right click in terminal to bring up context menu and you will see fullscreen is not checked. This requires you to click fullscreen in the context menu twice before leaving fullscreen.
I can go fullscreen via the context menu, via F11 and via the toolbar all in the same way, the check mark is always correct. No problem at all.
Created attachment 2426 Possible fix I can easily reproduce the beavhiour described by Adam by using the window manager menu. Not sure why it works for Christian, but the attached patch is a possible solution and quite trivial.
Applied a similar patch in revision 30138.