Do you mind if I ask what version of perl you're using? I seem to remember CGI.pm being added to the core distribution somewhere around 5.004, which was like 5 years ago. Any reasonably recent distribution of perl should already come with CGI.pm installed....
I'll have to check..it's 5.something...and it might have been "installed" but it wasn't functional...don't ask why..I don't have admin rights on the server all I know is it didn't work...then all of a sudden it appeared after I cried enough..and it started working :-)