The problem here is the lack of communication. How hard is it to show a brief popup telling the user what is happening and how to reverse it? At lot of applications with a fullscreen mode already do this. For example, Parallels and VMWare Workstation do it[1]. Options that can be confusing or dangerous should come with warnings instead of just taking them away.

[1]I think there is a way to stop showing the message, though.

Opera does it and offers an opera:config checkbox to turn the warning off.

Firefox is one the few who does not offer this feature.

Chrome does that when you hit F11.

in fact if you mouse to the top of the screen you can move away from full screen also