in reply to Search and replacing across 500,000 HTML documents

If you're using HTML::TokeParser, I fail to see the problem. Once you've gotten your page parsed, e.g.:
my $p = HTML::TokeParser->new(\$page_content);
Just check using the get_text method:
my $text = $p->get_text; if ($text =~ /$my_name/) {#stuff...}
Inside some while loop... You can use "get_tag" before and make sure to replace only in tags that you know wrap plain text (div, p, etc.).

Does this help?