Oh my goodness. I just tried
http://github.com/dme/notmuch/raw/dme-play/emacs/notmuch-address.el
together with the latest version of my "addrlookup" tool (which does the
same as jkr's notmuch_addresses.py) and it just works, even in current
cworth/master.

Address completion for to: and cc: headers based on my notmuch database,
sweet! Thanks David. I only need to reverse the sort order of addrlookup
as this uses most-to-least likely (which is more intuitive than eudc's
least-to-most likely sort order).

BTW, addrlookup now first tries to find matches that I previously sent
mails to and failing that it will try to find matches for all from:
addresses that match the search.

It would be trivial to include cworth's 3rd pass (or rather the 1st one)
of checking entries with an "address book" tag first. Which would
satisfy his entry in the notmuch TODO :-). which tag would make most
sense? And if a message had such a tag, would that mean the to: or the
from: is in the address book? Carl? It's your idea :-)

Sebastian