I've enabled that key combination, and I can now make gedit fullscreen with alt+f11 so I think that's working properly (this is nifty; wonder how I missed it..).
Pressing alt+f11 when windows firefox thinks it's in fullscreen mode has no effect. xprop shows no _NET_WM_STATE.
However, it does work (sort of) if I press it when firefox is not in fullscreen mode, except that I can see part of the bottom panel (but can't interact with it; I assume it's really firefox's window there but firefox hasn't drawn anything). xprop does show _NET_WM_STATE_FULLSCREEN when I do that.
I'm not aware of anything different about how wine sets fullscreen from other programs that I know work with metacity (I've compared the source code and as far as I can tell it's identical, unless wine is doing something else I'm not aware of).
Yeah, that looks really odd. That alone almost certainly means there's either a bug in KWin, metacity, or the EWMH. Could you try something for me to see if we can narrow down the cause? There's a special keybinding in Gnome, disabled by default, for manually setting windows to fullscreen mode. Could you run gnome-keybinding-properties, find the "Toggle fullscreen mode" item in the list, click on it, press some special key combo (e.g. Alt-F11), then focus your window in question, and press that key combo? That should make the window fullscreen and place it on top. If you could check the xprop thing again at that point just to verify the _NET_WM_STATE, that would also help.
After we know that, we can try seeing if you're setting the state in a weird way that KWin accepts but other WMs don't, or are setting it in a valid but slightly different way that Metacity should accept but doesn't, or if Metacity is doing something else weird.
Cheers, Elijah