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!)