The following works for the test cases I've tried:

use warnings;
use strict;

my %afterLists;
my %currItems;
my @itemList;
my $setNum = 0;

while (<DATA>) {
    chomp;
    next if ! length;
    
    if (/start/i) {
        @itemList = ();
        %currItems = ();
        ++$setNum;
        next;
    }
    
    if (! exists $currItems{$_}) {
        my %unique;
        
        $afterLists{$_} = [] if ! exists $afterLists{$_};
        @unique{@{$afterLists{$_}}} = ();
        @unique{@{$afterLists{$_}}} = () for @itemList;
        @unique{@itemList} = () if @itemList;
        if (exists $unique{$_}) {
            print "$_ order is inconsistent in set $setNum with a prev
+ious set\n";
            delete $unique{$_};
        }

        $afterLists{$_} = [keys %unique] if keys %unique;
        $currItems{$_} = 1;
        push @itemList, $_;
    } elsif ($currItems{$_}++ == 1) {
        print "$_ found multiple times in set $setNum\n";
    }
    
}

my @ordered = sort {$#{$afterLists{$a}} <=> $#{$afterLists{$b}}} keys 
+%afterLists;
my %lengths;

push @{$lengths{scalar @{$afterLists{$_}}}}, $_ for @ordered;

my @indeterminates = grep {scalar @{$lengths{$_}} != 1} keys %lengths;

print "The order of @{$lengths{$_}} can not be determined\n" for @inde
+terminates;
print "@ordered";

__DATA__
Start
Alpha
Beta

Start
Epsilon
Zeta

Start
Beta
Gamma
Zeta

Start
Alpha
Epsilon
Gamma

Start
Zeta
Gamma
[download]

Prints:

Gamma order is inconsistent in set 5 with a previous set
The order of Zeta Gamma can not be determined
The order of Beta Epsilon can not be determined
Alpha Beta Epsilon Zeta Gamma
[download]