What about something like this?:

%cat = (
   'C[AEIOU]NWAY' => 'AAA',
   '(?:BOSTON|CHICAGO)' => 'BBB',
   '(?:LAS VEGAS|NEVADA)' => 'CCC',
   '(?:DALLAS|AUSTIN)' => 'DDD',
   '(?:NASHVILLE|M[AEIOU]MPHIS)' => 'EEE'
);
$var = "CHICAGO";
@keys =  keys %cat;
$re = "(".join(")|(", @keys).")";
if ($var =~ /$re/o) {
  for ( 1 .. @keys) { 
    print "$_:", $$_, " - ",  $keys[$_-1], "\n" if defined $$_ }
}
[download]

Problems:

• It's not strict refs.
• it still loops on the number of matches (thought it only does one regexp match).
• I had to change all the '('s in the data to '(?:'.

I think the for loop could be replaced with one of the magical $+ or $- vars, but I couldn't find exactly the one I'm looking for - "The var that tells me how many of $1, $2 were defined in the last match".

-- Dan