的外れだったらごめん。前回の検索文字列は次のアンカーに書き出すときに
URIエスケープしてなくない？

printf qq(<a href="%s">次の10件</a>), URI_Escape($search_value);

### URIエスケープ文字列を返す
sub URI_Escape {
my($string) = @_[0];
$string =~ s/(\W)/'%' . unpack('H2', $1)/eg;
return ($string);
}