>> What does (frame-text-height) return for the first and the
 >> second frame?
 >
 > 1260 for both.

Relieving.

 >>    Also I hope you didn't get the GTK assertion failure.
 >>
 >
 > Indeed, I do not.

So the sequence definitely is: For some inexplicable reason we receive a
ConfigureNotify event that tells us that the frame has become very
small.  We accept the new size, adjust our frame accordingly and use the
new size as base for the next resize request.  When we issue that
request, GTK complains that it cannot fit the menubar and issues the
assertion failure.

 > When I do M-x menu-bar-mode the first time it has no effect, as Emacs
 > considers the menu bar to be currently enabled, so it disables it.

Since you run with

emacs -Q  --eval "(setq default-frame-alist '((menu-bar-lines . 0)))"

Emacs considers menu bars to be currently enabled "globally" and
disabling them globally has no effect on that frame.  Do you agree with
this explanation?

 > OK, running with just this patch (which applies fine), and doing the
 > history test, the history of the second frame is:
...
 > ConfigureNotify, PS=1328x1260, XS=400x376, DS=1328x1260
 > xg_frame_resized, rejected, PS=1328x1260, XS=400x376, DS=664x630

The 400x376 are as before so other size hints won't fix anything (but we
inherently checked that when running with 'frame-resize-pixelwise'
before).

 > menu-bar-lines (2), MS=160x175
 > xg_frame_set_char_size, visible, PS=1328x1260, XS=1328x1260, DS=1328x1260
 > ConfigureNotify, PS=1328x1260, XS=1328x1260, DS=1328x1260
 > xg_frame_resized, rejected, PS=1328x1260, XS=1328x1260, DS=664x655

But this one ...

 > tool-bar-lines (2), MS=160x175
 > xg_frame_set_char_size, visible, PS=1328x1260, XS=1328x1260, DS=1328x1260
 > ConfigureNotify, PS=1328x1260, XS=1328x1260, DS=1328x1260
 > xg_frame_resized, rejected, PS=1328x1260, XS=1328x1260, DS=664x696

... and this one are obviously fishy.  The sizes apparently match, so
why reject them?  The reason is that I recorded scaled sizes in what
appear after DS.  Since you have a scaling factor of 2 and (* 2 664)
gives 1328 this explains the width value.  The height value is likely as
(- (* 2 696) 132) giving 1260 where 132 is the height of your tool bar
(I extracted that from your previous call of 'frame-geometry').  If
there were a menu bar, we would have to subtract another 50 pixels.

So please try again with the attached patch which records the original
unscaled sizes.  And please tell me what

(frame-char-width)
(frame-char-height)

evaluate to.  I'm still trying to explain the 400x376 values.

martin