If you're conditions are simple enough, turning your structure inside-out will help I think.

my $rules = {

  'not in shift' => { allows    => [ 'Register for shift', ],
                    },
                  
  'in shift'     => { allows    => [ 'Confirm in shift',
                                     'Remove from shift',
                                   ],
                    },

#  'current'      => { # nothing seems to depend on current
#                    },
                  
  'past'         => { disallows => [ 'Remove from shift',
                                     'Register for shift',
                                   ],
                    },


};

sub get_menu_items {
    my ($rules,@conditions) = @_;
    my %results;
    
    for my $cond ( @conditions ) {
        next unless exists $rules->{$cond}; # irrelevant condition

        for $item ( @{$rules->{$cond}->{allows}} ) {
            $results{$item}++;
        }
        for $item ( @{$rules->{$cond}->{disallows}} ) {
            delete $results{$item};
        }
    }
    return keys %results;
}

my @conditions = ( ['in shift', 'past' ],
                   ['in shift', 'current' ],
                   ['not in shift', 'past' ],
                   ['not in shift', 'current' ],
                 );

for (@conditions) {
    my @result = get_menu_items($rules,@$_);
    print "Conditions: " . join(',',@$_) . "\n"
        . "Menu items: " . join(',',@result) . "\n\n";
}
[download]

And the results:

Conditions: in shift,past
Menu items: Confirm in shift

Conditions: in shift,current
Menu items: Remove from shift,Confirm in shift

Conditions: not in shift,past
Menu items: 

Conditions: not in shift,current
Menu items: Register for shift
[download]

This may just be a cheap application of others' suggestions to use boolean algebra and a state machine (or maybe not). I'm just a fan of code examples.

I DO think this is a very natural way for people to express rules in external config files.