Please find attached a patch series that add support for messages that lack Message-ID to notmuch-mutt, kindly provided by Jan N. Klug. I've reviewed / adapted it, and I consider it suitable for inclusion into the next release of notmuch(-mutt). Please let me know if you've any question. Cheers.