Hmmm...

DOCKS are at the always on top level, and we want panels to not obscure
fullscreen windows.  We could get the behavior you want by saying docks have a
different layer than always on top ones, and always on top trump fullscreen. 
But I think most people use always on top for windows such as gkrellm and such
in order to act like panels.  So we wouldn't want those windows to obscure
fullscreen things.  Typically, fullscreen is used for video players and such
which we don't want obscured.

I can't think of a good way to get the behavior you want without either ruining
the majority use case or making things much more complex.  I'm leaning towards
writing off this niche use case, but I'm open to better ideas.  The only thing
that occurs to me right now would be to introduce a second fullscreen-like state
for apps to use and set hints on.  It'd have to be in the EWMH, or else it'd
just be a hack that doesn't work for all apps (and even then, would panels be
able to obscure such windows?).  But having two fullscreen states with almost
identical meaning and only differing in "whether it's okay for the window to be
obscured" seems suboptimal--especially since it'd be difficult to differentiate
what is allowed to obscure it (panels vs. other windows marked as
always-on-top).  Got any bright ideas?

Elijah: I think you misunderstood the problem. I'm perfectly fine with always on
top not being on top of fullscreen. The problem is that when you leave
fullscreen, always on top is not on top. Okay, I guess it isn't clearer :-)

Let's try an example:

  +-------+
+---+     |
+---+     |
  +-------+
Figure 1. Two windows, small window is always on top

Let's say the small window is always on top. Now, I make the big window fullscreen:
+-------------+
|             |
|             |
|             |
|             |
+-------------+
Figure 2. Fullscreen

We don't see the small always on top window and I'm fine with this. Ok, now, I
want to leave fullscreen. I expect to have the same thing than in figure 1. But
I get this:

  +-------+
+-|       |
+-|       |
  +-------+
Figure 3. Two windows, small window is always on top, but metacity is wrong!

Now this should be clearer :-)
I should consider starting a new career in ASCII art...

Ah, I see and I can duplicate too.  Yeah, we need to fix that.

Ok, found the problem.  meta_window_unmake_fullscreen sets window->fullscreen to
FALSE, then updates the layer (meta_window_update_layer()), and then it resizes
the window (meta_window_move_resize()) to its original size.  This sequence
causes problems in computing the layer because of this snippet of code:
  else if ((window->fullscreen || window_is_fullscreen_size (window)) &&
  ...
Since the window hasn't been resized yet, it is still believed to be fullscreen
size even if it isn't fullscreen--and is thus thrown in the fullscreen layer.

I'll attach a patch in a minute.

Created attachment 36749 [details] [review]
Resize the window before updating the layer

committed.