Basically, greediness is only one consideration for how regexps find their matches, and in this case it's not affecting your results. What perl is doing is first looking for the first < character, then when it finds it, it looks forward (non-greedily) for the first matching >. There are a few ways around this, but I think what you might find best would be

$str = 'Some TextVenture</B Brothers</a>';
$str =~ s/<[^<]*>//;
[download]

Update: See How will my regular expression match? for more details on why greediness isn't the only factor.