What does the respective raw query look like when you encounter the problem, i.e. $ENV{QUERY_STRING} with GET requests? In other words, are you sure it's CGI.pm that's responsible for the encoding?

Also, as you describe things, it sounds as if this is a new phenomenon. So, has there been a version change of CGI.pm lately? Which version is it, anyway?