Regarding whether or not messy internals are a reason not to use something, if I may be so bold as to suggest that Perl 5's internals are a bit of a mess. That's part of the impetus behind Perl 6, but Perl 5 works and I'm not going to stop using it :) You also might find the following thread on that subject of interest: Paradigm Shift - Don't use strict.
If you're going to suggest alternatives, don't forget CGI::Simple by tachyon. It's an excellent module and, more importantly, it's a drop-in replacement for CGI.pm. It seems to meet the requirements you specify and it since it's a drop-in replacement, it has an interface that most CGI programmers are already familiar with. In fact, I might even vote it "most overlooked module".
New address of my CGI Course.
Silence is Evil (feel free to copy and distribute widely - note copyright text)