Você pode e deve usar o campo Message-ID no cabeçalho. Para facilitar, basta personalizar sua pesquisa.
Ir para Editar - > Encontre - > Pesquisar mensagens. A partir do campo de busca selecione a última opção "Personalizar ...", na caixa de texto do novo apperead Window escreva Message-ID e clique em Add e depois em OK (testado no Thunderbird 11.0.1).
Agora você tem um novo campo para pesquisar, selecione-o e escreva seu ID no campo de pesquisa e Voilà.
Eu faço isso para conectar uma lista "TODO" a um e-mail. A pesquisa é confiável e mais rápida que "From + Subject".
Gostaria de poder adicionar isso a "Pesquisa rápida ...".