Thanks for digging deeper. I didn't have a need for PUT or DELETE yet (but I reckon I will in the future), so I hadn't realised the support was this limited.
I agree that a patch to CGI is in order. Even if most web browsers don't support them, PUT and DELETE are still valid HTTP verbs, and I feel that the various CGI modules ought to support them.
At first blush, a patch to either CGI or CGI::Simple doesn't look so difficult. I think DELETE could be handled pretty much the same way as GET, and PUT is pretty similar to POST. I may be overly optimistic, but it shouldn't take more than changing a couple of if()s ;-)