After checking perldelta for 5.005_3 and Elements of Programming with Perl, I have to conclude that lookbehind assertions were introduced in 5.005. Lookaheads were around before that, though.
As to why perlre for 5.004 shows that -- your guess is as good as mine.