I've recently signed up with rackspace.com so that I could write and host some simple Perl scripts( johnnycarlos.com for the curious).

It's $11 per month, plus additional bandwidth for a 256MB RAM, 10 GB hdd linux server. I was really impressed with how easy and quickly I was able to create an account, spin up a server, and get my own IP address... it was a matter of minutes and I was up and running.

Now, if by "supports Perl CGI" you mean: you want to install your own modules and versions, then this is a great solution because you are the server owner, you are root, and you do whatever you want with it.

But if by "supports Perl CGI" you mean you want to call someone and ask for help, you're probably not going to find anything like that without paying a WHOLE LOT of money to someone like Redhat for enterprise support.