$self->{__Taintless_param_check} = "^\(\[\\w\\\_\]\{1\,$max_param_len\}\)\$";

I think it's hard to get the number of backslashes right. Maybe you want to use qr{...} instead? Also $ in a regex allows a trailing newline before the end of the string - is this what you want? If not, use \z instead.

Somehow I think that CGI::Taintless isn't a very good name at all. Your focus should be on validating CGI params, with the side effect of untainting them. Maybe something along the lines of CGI::RegexValidate might be more appropriate as a name?

Note that passing unvalidated CGI params to the output is a security risk, because it allows cross-site-scripting - unless you escape it. So the tests in your sample program fail for a good reason.

Usually I take the approach of trying to validate as little as possible, because I don't know how to validate. If there's a field for the real name of a user, how do you validate that? And if you do it, are you sure that all possible names in all human languages (of which there are quite many) are actually accepted? How do you test that?

Instead I use placeholders for my DB queries, and set the default_escape option of HTML::Template (or HTML::Template::Compiled) to html, and care as little as possible about the contents of the fields.

So for me this module makes only very little sense, but of course I can't speak for everyone, and I can well imagine that other perl hackers might find it useful.