I don't know about improving the performance, but the code can be cleaned up. Consider:

use strict;
use warnings;

my %fieldNameMapping;
my @recentLines;

fetchLines (\@recentLines, 2);

while (fetchLines (\@recentLines, 1)) {
    next if($recentLines[-3] !~ /Level \(1\) "([^"]+)"$/);
    next if($recentLines[-2] !~ /Level \(2\) "([^"]+)"$/);
    next if($recentLines[-1] !~ /Record \(([0-9]+)\) "([^"]+)"$/);

    my $recordID = $1;
    my %recordBodyToWriteOut ;
    my $recordHeader = "RECORD\n"; # First value in the header
    $recordHeader .= "#addkey\n#filename FF\n#input_id 001\n";

    do {
        if(nextLine (\@recentLines) =~ /"([^"]+)" = "([^"]+)"$/) {
            if($1 eq 'MSC_CDR_TYPE') {
                $recordHeader .= "#input_type $2\n#output_id\n#output_
+type $2\n#source_id SRC\n";
            }
           
            if(exists $fieldNameMapping{$1}) {
                $recordBodyToWriteOut{$fieldNameMapping{$1}} = $2;
            } else {
                $recordBodyToWriteOut{$1} = $2;
            }
        }
    } until
           ($recentLines[-3] =~ /End of Record \(${recordID}\)$/)
        && ($recentLines[-2] =~ /End of Level \(2\)$/)
        && ($recentLines[-1] =~ /End of Level \(1\)$/);

    my $recordTrailer = ".\n";  # First value in the Trailer
   
    fetchLines (\@recentLines, 2);
    print $recordHeader;

    foreach my $key (sort keys %recordBodyToWriteOut) {
        print "F $key " . $recordBodyToWriteOut { $key } . "\n";
    }

    print $recordTrailer;
}


sub fetchLines {
    my ($lines, $toFetch) = @_;
    my $fetched = 0;

    while ($toFetch-- > 0) {
        my $newLine = nextLine ($lines);
        return $fetched > 0 if ! defined $newLine;
        
        ++$fetched;
    }
    
    return 1;
}


sub nextLine {
    my ($lines) = @_;
    my $line = <DATA>;
    
    return undef if ! defined $line;
    
    push @$lines, $line;
    shift @$lines while @$lines > 3;
    
    return $line;
}

__DATA__
Start of Data
**********************************************************************
Level (1) "COMMONRec"
   Level (2) "MSCCDR"
      Record (1) "MSCGSMRec"
         "MSC_CDR_TYPE" = "MOC"
         "MSC_CALL_START_TIME" = "20090122105929"
         "MSC_CALL_END_TIME" = "20090122105944"
         "MSC_CALL_DURATION" = "15"
         "MSC_PARTIAL_INDICATOR" = "S"
         Sub Record (1) "AXECallDataRecord"
            "AX_DISCONNECT_PARTY" = "1"
            "AX_CHARGED_PARTY" = "0"
            "AX_TRANSLATED_TON" = "1"
         End of Sub Record (1)
      End of Record (1)
   End of Level (2)
End of Level (1)
Level (1) "COMMONRec"
   Level (2) "MSCCDR"
      Record (2) "MSCGSMRec"
         "MSC_CDR_TYPE" = "MTC"
         "MSC_PARTIAL_TYPE" = "0"
         "MSC_CALL_START_TIME" = "20090122105927"
         "MSC_CALL_END_TIME" = "20090122105945"
         "MSC_CALL_DURATION" = "18"
         "MSC_PARTIAL_INDICATOR" = "S"
         Sub Record (1) "AXECallDataRecord"
            "AX_DISCONNECT_PARTY" = "1"
            "AX_CHARGED_PARTY" = "0"
            "AX_SWITCH_IDENTITY" = "0001"
            "AX_RELATED_NUMBER" = "7F4595"
            "AX_FIRST_CALLED_LOC_INFO" = "25F010233203BE"
         End of Sub Record (1)
      End of Record (2)
   End of Level (2)
End of Level (1)
[download]

Prints:

RECORD
#addkey
#filename FF
#input_id 001
#input_type MOC
#output_id
#output_type MOC
#source_id SRC
F AX_CHARGED_PARTY 0
F AX_DISCONNECT_PARTY 1
F AX_TRANSLATED_TON 1
F MSC_CALL_DURATION 15
F MSC_CALL_END_TIME 20090122105944
F MSC_CALL_START_TIME 20090122105929
F MSC_CDR_TYPE MOC
F MSC_PARTIAL_INDICATOR S
.
RECORD
#addkey
#filename FF
#input_id 001
#input_type MTC
#output_id
#output_type MTC
#source_id SRC
F AX_CHARGED_PARTY 0
F AX_DISCONNECT_PARTY 1
F AX_FIRST_CALLED_LOC_INFO 25F010233203BE
F AX_RELATED_NUMBER 7F4595
F AX_SWITCH_IDENTITY 0001
F MSC_CALL_DURATION 18
F MSC_CALL_END_TIME 20090122105945
F MSC_CALL_START_TIME 20090122105927
F MSC_CDR_TYPE MTC
F MSC_PARTIAL_INDICATOR S
F MSC_PARTIAL_TYPE 0
.
[download]

Notes:

our is not used at all. Use my instead. I doubt our does what you think it does.

Bail as soon as possible instead of nesting conditional code. The logic is easier to follow and easier to get right.

Declare variables where they first get a real value. That is, make their scope as small as possible.

Don't provide default values for variables, unless it really is a default. In particular, Perl generates arrays and hashes empty and scalars with the value undef - you don't have to do that explicitly.