Morning update.  After the gdb debacle yesterday (gdb needs some work... :-(), I made the following changes.
1) Recompile gtk+ with --enable-debug=all (because GDK_DEBUG wasn't working);
2) Setup firefox-3.0a2 (with all the debug code) to run with:
     export NSPR_LOG_MODULES=Widget:4
     export NSPR_LOG_FILE=nsprlog.txt (= the Netscape error log)
     export GDK_DEBUG=events
     export GOBJECT_DEBUG=objects
       (GOBJECT_DEBUG may not be important for this problem but does seem
        to reveal some interesting problems with GLIB "leftovers" when
        firefox exits).
     firefox-bin 2>firefox.err (= the GDK error log)
3) Run firefox restoring the previous session (which had demonstrated the problem).

Now, the session that first showed the problem had 73 windows & 424 tabs.  When gdb went belly up I was up to 76 windows and 438 tabs (demonstrating the tab-start=>"untitled window" problem with some frequency but not every time).

I'm now up to 100 windows and 586 tabs (mainly using random URLs from the first 25 pages of Digg) with firefox-bin consuming 1.1 GiB of VM and 1.2 GiB Mem (is this including page tables???).  No problem.  I can't push this much further because I normally run firefox with a 1.4 GiB virtual memory limit (ulimit -Sv 1400000) -- due to Firefox's poor handling of memory allocation failures it will likely core dump if I push it to 1.4.  (If one allows Firefox VM >> system PysMem (1.5 GiB for me) ==> watch the system turn into a dog -- but this is really a Linux paging problem somewhat aggravated by the Firefox heap management problems so not for this discussion).

Firefox has been running for ~12 hours.  I ran it for a while with Java and Javascript disabled (because the logging seems to slow down new tab/window creation), but Javascript is now enabled without making much difference.  One difference may be that the AdBlock addon may not have been active in the previous instance when the problem did occur.  Noscript is active and is blocking Javascript on most sites (gmail exempted).  Gmail works fine (and it tends to be a moderately reliable "helper" (?) in my case to trigger the problem state).

CPU-wise firefox-bin+X are consuming 40-60% of the CPU time.

The debug log files (for NSPR & GDK) are rather large (10's of MB).  I am concerned that outputing the debug messages has changed the timing of Firefox+GDK/GTK/GLIB+X just enough to make the problem "disappear".

I'm not sure I understand yet the discussion of the nsWindow code, but would argue that until we know *precisely* where the DestroyNotify is coming from and why it is happening it may be difficult to know whether changing the upper level code has fixed or simply masked the real problem.  But given the number (5362) of "Gdk-Message: destroy notify" events I'm seeing in the GDK log file, it isn't going to be as simple setting a breakpoint in gdkevents-x11.c::gdk_event_translate():case DestroyNotify.  What one needs is a stack trace for the DestroyNotify that is at the start of the "untitled window" error sequence (which is presumably different from all of the other DestroyNotify stacks).  Given the problem of logging perhaps changing subtle timing requirements for the problem to occur it isn't clear that one could simply stick some stack tracing code into the DestroyNotify code.

Even if one fixes the nsWindow code so it works, that doesn't explain why it works almost all of the time now but fails in these random cases (when the CPU load is too heavy?  when Javascript has fragmented the heap?  when some race condition occurs in GDK/GLIB?)

One question might be whether there is an explicit way when Firefox is running to stop asynchronous activity (e.g. garbage collectors, which I presume are in separate threads)?  (In the fragmented heap situation, I presume that these will contribute to excessive CPU consumption by firefox, so it would be useful to (a) create the problem state; (b) turn off async CPU consuming threads; (c) see if the probability of the problem taking place diminishes).

It would also be nice if there were some in-place hooks so that one could put the stack trace code into the DestroyNotify code, restart firefox with an error-prone session and then hit the process with a SIGUSR1 to activate the DestroyNotify stack tracing after one has encountered the problem the first time.  At least then one would be dealing with perhaps dozens of traces rather than thousands.