Method calls ignore subroutine prototypes, so you can safely delete them.

search_tag() is awfully long. I'd decompose it into several helper methods.

You have several blocks that could be shortened. I'd write this:

if (!defined ($tag_search) &&  !defined ($attr_search))
{
    $ok = 0;
    return($ok, "No values for tag searched");
}
[download]

as

return (0, "No values for tag searched")
    unless defined $tag_search and defined $attr_search;
[download]

As well, you can fetch a single element from an array reference more idiomatically:

my $tag   = @{$tagstruct}[0];
# versus
my $tag   = $tagstruct->[0];
[download]

There are some exit conditions inside your loop that seem to be known before you enter the loop. In this case, you're better off not looping at all. I think if you extracted a few methods the control flow would be more clear and you might see what I think I see. (Or I might not really see it :).

Within check_response(), you have two nearly-identical loops. I'd rather write:

use HTML::TokeParser;

my @forbid  = $self->test_tags( 'tag_forbid', $content, $case_re );
push @ret, ['Forbidden tag and attribute', @results] if @forbid;

my @require = $self->test_tags( 'tag_require', $content, $case_re );
push @ret, ['Required tag and attribute', @results] if @require;

sub test_tags
{
    my ($self, $tag_type, $content, $case_re) = @_;

    my $page = HTML::TokeParser->new(\$content);

    my @results;
    for my $tag_struct (@{$self->test_param( $tag_type, [] )})
    {
        my ($ok, $result) = search_tag( $page, $case_re, %{ $tag_struc
+t });
        push @results, $self->test_result($ok, $result);
    }

    return @results;
}
[download]

I'd rather pass $tag_struct directly, but that'd change the API and I'm not going to do that right now.