a tale of three tools: mairix, maildir-utils (mu), nmzmail
I think/fear I'm getting into this Getting Things Done thingie. For weird reasons I'll explain later on, part of the GTD work flow I'm implementing requires quick lookup from Message-IDs to the corresponding mail, no matter in which mailbox (actually Maildir) I've stored it.
Hence, I've looked for a mail indexing tool which is Mutt-compatible, handles Maildirs, and supports Message-ID queries. In Debian (where else should I look? g), I found three: mairix, nmzmail, maildir-utils (whose upstream name is actually "mu").
The first one I tried is mairix. Last upload in Debian was 2 years ago, it doesn't seem to be particularly buggy, and in popcon it has about 300 installations. The integration with mutt is good: searches can create a sort of virtual Maildir, whose files are symlink to the search results; with a couple of macros you can have Mutt easily open the result directory after query. The reason why I ditched mairix, is that it heavily suffer from the NIH syndrome. mairix is a self-contained executable with no external dependencies; that in principle being good, I found nowadays totally unreasonable to not use some third party full text search indexer, given that in the FOSS world we have several good ones. A good aspect of mairix, which is missing in the competitors, is the ability to index messages incrementally as they flow in, e.g. via procmail. Still, the problem of that is that it is difficult to pair that with the habit of moving messages across mailboxes. To that end, periodic re-indexing, or better batch index updates, offers a better work flow.
Then I tried nmzmail, which claims at is killer feature the "better integration with Mutt" wrt competitors. Actually, this is false, it has the same level of integration of the other (virtual maildirs with macros) and it doesn't even offer a ready to use set of macros in the doc! (yeah, they're easy to write, but given that you claim you're so well integrated with Mutt ...). The reason why I ditched nmzmail is that I didn't particularly like its choice of (external at least) indexer: Namazu. The index it created was very big (something like 250 Mb for about 400 Mb of Maildirs). Also, I had a bad feeling that the indexing was somehow Japanese-specific (the project having support for that language) and I found no way to disable support for that, which I obviously do not need.
Finally, I tried maildir-utils and I was finally happy. It is implemented on top of Sqlite3 (for mail metadata) and Xapian (for full-text indexing). There are some bugs, but Norbert, as the very reactive maintainer, have tackled down most of them now and I've been happy to help with various feedback. Integration with Mutt is granted by the following 2 macros:
macro index <F8> "<shell-escape>rm -rf ~/.mu/results; mu-find -o l -l ~/.mu/results " "mu-find"
macro index <F9> "<change-folder-readonly>~/.mu/results\n" "display mu-find results"
The first one query (you) for the search string, the second jumps to the results opening the virtual Maildir (which is useful, especially when you want to go back to the last query you did). I update the index every two hour with the following cron entry:
31 */2 * * * on_ac_power && mu-index -q
Beside a corner case bug which is close to solution, updating the index is very fast, usually a few seconds; index size is about 150 Mb. To conclude, my initial goal (message path lookup via Message-ID) is easily achieved as follows:
$ mu-find -f P m:20091030112543.GA4230@usha.takhisis.invalid
/home/zack/Maildir/INBOX/cur/1256902638_0.25702.usha,U=37563,FMD5=7e33429f656f1e6e9d79b29c3f82c57e:2,S
In addition to that, I've now gained all-maildirs full-text
search from within Mutt 
As a concluding remark, Enrico pointed me to Not much mail, but it seems to be (by authors' own admission) in early stage of development. Also, AFAIU it aims to be a MUA, whereas I'm perfectly fine with Mutt, I just need from time to time to integrate it with other components of my daily work flow.
Update: (30/01/2011) I've now tried Notmuch and switched to it without looking back. I've written about it in a separate post, including tips on how to integrate Notmuch with Mutt.
