I submit:

qr %<p>([^<]*(?:<(?!b>|/p>)[^<]*)*)</p>%i;
[download]

and a benchmark. The solution with the lookahead on each character does much better than I expected:

#!/usr/bin/perl

use strict;  
use warnings;

use Benchmark qw /cmpthese/;

our $abigail = qr %<p>([^<]*(?:<(?!b>|/p>)[^<]*)*)</p>%i;
our $bart    = qr %<P>((?:(?!<b>).)+?)</P>%is;
our $corion  = qr %<p>((?:[^<]*|<(?!b>)[^>]+>)*?)</p>%i;

my @names = qw /abigail bart corion/;

our @data = <DATA>;

my @correct = ('Just another perl hacker',
               'this should match',
               'What about <a href="http://www.example.com">this</a>?'
+,
               'And <p>this');

cmpthese -1 => {map {$_ => "\@$_ = map {/\$$_/g} \@data"} @names};

no strict 'refs';
"@$_" eq "@correct" or die ucfirst for @names;


__DATA__
<P>Just another perl hacker</P>
<P>Just <b>another</b> perl hacker</P>
<p>this should match</p>
<p>This should <b>not</b> match</p>
<p>What about <a href="http://www.example.com">this</a>?</p>
<p>And <p>this</p> malformed piece?</p>



           Rate  corion    bart abigail
corion   6457/s      --    -68%    -72%
bart    19910/s    208%      --    -14%
abigail 23209/s    259%     17%      --
[download]

Abigail