When I first read about the idea to remove CGI.pm from core, I was like "Yeah!". And then I thought about it and I was like "meh".
Who cares? Your typical noob that needs to be protected from the horrors of CGI.pm is not the kind of guy who builds his own perl. He is also not the kind of guy who uses an up-to-date perl. He probably has some company server running 5.8 or he might use whatever his hoster installed. Before he learns that there even is a core, he'll have a zoo of spaghetti cgi-scripts that won't work when using strictures.
But here is someone who will care about a missing CGI: the package maintainers of all the Linux distros out there. They will have to decide whether to pack CGI.pm into their main perl-package or whether to put it in its own new package. Since there are about a gazillion packages that quietly depend on CGI.pm, their most likely choice will be the former option.
So what I am trying to say is: You will not kill CGI.pm by removing it from core. But removing it from core will also not be noticed by any kind of user who doesn't know how to use a cpan client.