Build a profile of the line and then use substr to extract the relevant data fields.

#!perl
use strict;
use Data::Dump 'pp';

my @fields = (
'PERMIT NO', 'VALUATION',
'PARCEL NO', 'ISSUED DATE',
'LOCATION',
'OWNER','CONTRACTOR');

my $match = join '|',map{ quotemeta }@fields;
my $re = qr/$match/;
#print $re."\n";

# %posn is fieldname => [startposn,length]
my %posn = (); 

# fields on one line
my @cols = ();

my $rec  = {}; # one record
my %data = (); # many records
while (<DATA>){
  # start new record
  if (/PERMIT NO/){
    add_record($rec);
    $rec = {};
  }

  # build profile
  if (/:/){
    @cols = ();
    while (/($re):/g){
      push @cols,$1;
      $posn{$1}[0] = pos();
      $posn{$1}[1] = 0; # to end of line
      
      # calc previous col length
      if (@cols>1){
        my $prev = $cols[-2];
        $posn{$prev}[1] = pos()-length($1)-$posn{$prev}[0]-1;        
      }
    }
  }
  
  # extract data
  for my $c (@cols){
    my $posn = $posn{$c}[0];
    my $len  = $posn{$c}[1];
    my $str = ($len) ? substr $_,$posn,$len
                     : substr $_,$posn;     
    $str =~ s/^\s+|\s+$//g; 
  
    #print "$c = '$str' $posn $len\n";
    $rec->{$c} .= ' ' if exists $rec->{$c} && $str;
    $rec->{$c} .= $str;
  }
} 
# last record
add_record($rec);
pp \%data;

# add record to %data
sub add_record {
  my $rec = shift;
  my $no = $rec->{'PERMIT NO'};
  $data{$no} = $rec if ($no);
}; 

# debug
#pp \%posn;

__DATA__
[download]

Update ; removed length for last field

you didnt show us, but somehow you are parsing into the 2 cols before this point, so somehow $column_line comes from column 1 or col 2. You somehow know what col you are in. lets say it is in $coln; so when if ($column_line =~ /:/) is true you save 2 keys $keys{1} and $keys{2} from the parts before the : via $keys{$coln}=$key; then the line becomes $data{$permit_no}{$keys{$coln}} .= $column_line;