I haven't had a chance to really track this down, but it seems there is a memory error in notmuch new (or a maybe false positive from valgrind). Attached is the log from running "make memory-test OPTIONS=--medium" on current git master (0e037c34). It looks like we talloc the message_id string with the message object as parent, but it somehow outlives the message object.