> However, with my way of handling CHARS_MODIFF, there is no need
 > for a separate SAVE_CHARS_MODIFF.  SAVE_MODIFF can be used.
 > If CHARS_MODIFF > SAVE_MODIFF, then the text in the buffer
 > has been altered.  If SAVE_MODIFF >= CHARS_MODIFF, then the
 > text has not been altered since the last save.

Yes.  If needed we can always add:

DEFUN ("buffer-chars-modified-p", Fbuffer_chars_modified_p, Sbuffer_chars_modified_p,
        0, 1, 0,
        doc: /* Return t if a character changed in BUFFER since its file was last read or saved.
No argument or nil as argument means use current buffer as BUFFER.  */)
      (buffer)
      register Lisp_Object buffer;
{
   register struct buffer *buf;
   if (NILP (buffer))
     buf = current_buffer;
   else
     {
       CHECK_BUFFER (buffer);
       buf = XBUFFER (buffer);
     }

   return BUF_SAVE_MODIFF (buf) < BUF_CHARS_MODIFF (buf) ? Qt : Qnil;
}

 >     +     int chars_modiff;		/* This counts insert/delete events
 >     + 				   for this buffer.  It is incremented for
 >     + 				   each such event, and never otherwise
 >     + 				   changed.  */
 >
 > That comment is not true for the current code.
 >
 >     Perhaps the cleanest solution would be to equip modify_region with an
 >     additional parameter, say preserve_chars_modiff, and do everything in
 >     modify_region.
 >
 > It might be better.  Please give it a try and see.

Please consult the attached patch.

Simon, please try with your settings whether the patch makes those extra
calls to `imenu-update-menubar' disappear.  For some strange reason, I
was not able to reproduce your behavior so far.