I've got a scheme that may fix this. Note that, since I
don't run windows, the code below is only schematic
(i.e. completely untested)

--- begin code ---

typedef struct _GdkWin32RectangleDrawInfo {
  GdkRectangle rect;
  GdkGC *gc;
  GdkDrawable *draw;
  gboolean filled;
  struct _GdkWin32RectangleDrawInfo *next;
} GdkWin32RectangleDrawInfo;

typedef struct {
  GdkWin32RectangleDrawInfo *cache;
  gboolean have_timeout;
} GdkWin32RectangleCache;

static void
gdk_win32_draw_rectangle (GdkDrawable *drawable,
                          GdkGC       *gc,
                          gint         filled,
                          gint         x,
                          gint         y,
                          gint         width,
                          gint         height)
{
  GdkWin32RectangleDrawInfo *cache_elem;
  static GdkWin32RectangleCache = {NULL, FALSE};

  if(cache->have_timeout == FALSE) {
    g_timeout_add(1, (GSourceFunc) gdk_win32_do_draw_rectangle,
      cache);
    cache->have_timeout = TRUE;
  }

  cache_elem = g_new(GdkWin32RectangleDrawInfo, 1);

  cache_elem->rect.x = x;
  cache_elem->rect.y = y;
  cache_elem->rect.width = width;
  cache_elem->rect.height = height;
  cache_elem->draw = drawable;
  g_object_ref(drawable);
  cache_elem->gc = gc;
  gdk_gc_ref(gc);
  cache_elem->filled = filled;

  cache_elem->next = cache->cache;
  cache->cache = cache_elem;
}

static gboolean
gdk_win32_do_draw_rectangle (GdkWin32RectangleCache *cache)
{
  GdkWin32RectangleDrawInfo *cache_elem;

  /* Draw implementation here */

  while(cache->cache) {
    cache_elem = cache->cache;
    cache->cache = cache_elem->next;
    g_object_unref(cache_elem->draw);
    gdk_gc_unref(cache_elem->gc);
    g_free(cache_elem);
  }

  cache->have_timeout = FALSE;

  return FALSE;
}

--- end code ---

Note that the timeout exists only when the cache has
something in it. It runs once, clears the cache,
and destroys itself.

You at least want to use an idle rather than a timeout, a timeout
probably guarantees more of a slowdown than the optimization avoids,
because of limited clock precision.

What Xlib does is flush the cache whenever you query the server for a
value or call XNextEvent(). One equivalent of this in GDK might be to
just flush the cache in the dispatch function for the GDK event GSource.

    Looking back, I also realized that you would need
to cache _all_ drawing to get things to draw in the
correct order.

I think this was included in gtk2 ...

Not as far as I know. (Note that this is about the win32 backend, 
for the X11 backend the accumulation of requests of the same
type occurs in the Xlib layer)

I very much doubt this is going to happen... Resolving as WONTFIX.