I have pushed a branch jlog 

  git://pivot.cs.unb.ca/notmuch.git

This uses the jlog library (http://labs.omniti.com/labs/jlog)
to atomically log messages in pub-sub model.

On this branch you can enable logging of tagging operations by 

   notmuch config set log.subscribers 'name1;name2;name3'

the "subscriber names" identify clients (one could imagine one client
deals with general tag syncing, another with nmbug, or so).
  
One can read the log via the jlog api (there are perl bindings) or via
the "notmuch log" command. 

    notmuch log name1 

will print all of the log messages since the last time the queue was
read.

for e.g., tag removal, these lines look like

T-1322702130-26068-3-git-send-email-bremner@debian.org test
T-1322702130-26068-1-git-send-email-bremner@debian.org test
T-7fbe6befcf31881a9bca672f55b93501249a220c.1322859389.git.jani@nikula.org test
T-716da00e176e1dc6af0ba248caee40acee733120.1322859389.git.jani@nikula.org test

An example application would be a cron job that writes all tag changes
to some nmbug like git repo.

There are a few rough edges and I expect to rebase the branch a bit
more, but feel free to have a look at it.  I guess I'm curious if people
think jlog is an acceptable dependency, and whether the whole logging
thing seems worthwhile. 

I did some preliminary tests, and for adding or deleting a tag to 200k
messages, this added about a 5% time penalty. I didn't notice any really
heavy I/O (no SSD here, but i7 cpu). Tests were roughly 95% CPU bound.

There are some preliminary debian packages for jlog at 

      git://pivot.cs.unb.ca/jlog.git

The upstream source for jlog is at 
    
    https://github.com/omniti-labs/jlog