Well, we're already packaging our own CGI.pm, so... ;)

Unfortunately, it's the 5.004 bit that's the limit, not the lack of modules. Parse::RecDecent, for instance, requires 5.005.