Sometime this week, Nuno asked me for a reference to that tool, and I just could not find it. I'm now pretty much sure that I was dreaming about it.
But the idea nagged me for a couple of days, and today I broke and took Mail-tools and KinoSearch for a ride.
The result is maildir_indexer.
Right now it works. It indexes about 100 messages per second on my laptop. Searching is instantaneous. I'll index about 10Gb of mail tomorrow to have better numbers. The index size is about 1/3 of the data.
This was a quick hack and it shows. Feel free to send patches, but look at the future/todo list first.