The problem seems to be you have a linked list, but as it exits it's only reverse. I would start by scanning the file and building a hash as you started but put more in the hash. 
$hash{$msgid} = {
    filepos => $msgstart,
    inreply => $msgreply,
    nextmsg => []  # reference to an empty array
}

[download]
Then I'd scan the hash keys and build the forward links 
my @heads;
while(my ($key, $value) = each(%hash)) {
    # does this msg have a parent?
    if (my $parent = %hash{$value->{inreply}}) {
        # link the parent to this message
        push @{$parent->{nextmsg}}, $key;
    }
    else {
        # no parent so it must become a thread start
        push @heads, $key;
    }
}

[download]
Finally, I'd loop through @heads to get the message threads. 
foreach my $msgid (@heads) {
    # do what ever you have to do to start a new thread
   
    # recursively follow the messages
    thread_msgs($hash{$msgid});
}

# recursively read through the thread
sub thread_msgs {
    my $msgid = shift;

    # use seek() to position the mbox file at
    # the message start using $msgid->{filepos}
    # copy to the end of the message

    foreach $msgid (@{$msgid->{nextmsg}}) {
        thread_msgs($msgid);
    }
}

[download]
Note that this preserves the thread of messages replied to messages, but it doesn't preserve the order of messages. You may want to sort by message id when it comes time to copy the messages. (also note I haven't tested this!)

In reply to Re: Organising mbox into threads? by ruzam
in thread Organising mbox into threads? by LoonyPandora

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.