Here are some benchmarks: (fixed from TLM's)

use strict;
use warnings;

use Benchmark 'cmpthese';

my $sz      = ( shift || 10 ) - 4;
my $X = 'N' . 'x' x $sz . '000';
my $Y = 'N' . 'x' x $sz . '001';

print("X = $X\n");
print("Y = $Y\n");
print("\n");

cmpthese( -1, {
'/^N(?!.*00$).*$/ failure' => sub { scalar $X =~ /^N(?!.*00$).*$/ },
'/^N(?!.*00$).*$/ success' => sub { scalar $Y =~ /^N(?!.*00$).*$/ },
'/^N(?!.*00$)/    failure' => sub { scalar $X =~ /^N(?!.*00$)/    },
'/^N(?!.*00$)/    success' => sub { scalar $Y =~ /^N(?!.*00$)/    },
'/^N.*(?<!00$)$/  failure' => sub { scalar $X =~ /^N.*(?<!00$)$/  },
'/^N.*(?<!00$)$/  success' => sub { scalar $Y =~ /^N.*(?<!00$)$/  },
'/^N.*(?!00)..$/  failure' => sub { scalar $X =~ /^N.*(?!00)..$/  },
'/^N.*(?!00)..$/  success' => sub { scalar $Y =~ /^N.*(?!00)..$/  },
});
[download]

Results:

X = Nxxxxxx000
Y = Nxxxxxx001

/^N.*(?!00)..$/  failure 278229/s     -- 
/^N.*(?<!00$)$/  failure 330512/s    19%
/^N(?!.*00$).*$/ success 536004/s    93%
/^N.*(?!00)..$/  success 540980/s    94%
/^N(?!.*00$)/    success 633900/s   128%
/^N(?!.*00$)/    failure 743994/s   167%
/^N(?!.*00$).*$/ failure 750772/s   170%
/^N.*(?<!00$)$/  success 789866/s   184%
[download]

Combined success and failure results:
(If the numbers are evenly distributed, the chance of failure is 0.01.)

/^N(?!.*00$).*$/  750772/s * 0.01 + 536004/s * 0.99 = 538151.68/s   --
/^N.*(?!00)..$/   278229/s * 0.01 + 540980/s * 0.99 = 538352.49/s   0%
/^N(?!.*00$)/     743994/s * 0.01 + 633900/s * 0.99 = 635000.94/s  18%
/^N.*(?<!00$)$/   330512/s * 0.01 + 789866/s * 0.99 = 785272.46/s  46%
[download]

/^N.*(?<!00$)$/ is the winner as expected, and it won by no small margin (24%).