Encadeamento GMail, IMAP e Ruby

Eu estou usando a biblioteca IMAP Ruby para obter uma conversa GMail. A maneira como o GMail encadeia as conversas é através dos cabeçalhos das mensagens "Message-ID" e "In-Reply-To". Por exemplo:

In-Reply-To: <c0f07c940909151905w1ad93fabx19cf595f653c8b@mail.gmail.com>
Message-ID: <9cd2f5ff0909151911r30ddb805n5172970dffc872c2@mail.gmail.com>

Não consigo descobrir como obter de forma eficiente a mensagem respondida. A maneira atual:

target = <c0f07c940909151905w1ad93fabx19cf595f653c8b@mail.gmail.com>
imap.search(["NOT", "DELETED"]).each do |msg_id|
  uid = imap.fetch(message_id, "ENVELOPE")[0].attr["ENVELOPE"].message_id
  if uid == target
    m = imap.fetch(msg_id, "RFC822")[0].attr["RFC822"]
  end
end

Demora muito tempo para fazê-lo sequencialmente assim, mas não consigo descobrir o encantamento correto para pesquisar pelo cabeçalho da Mensagem-ID, e realmente não consigo encontrar nenhuma evidência sobre se isso é possível ou não.