Perl has many templating systems which work in the same way as PHP. They don't require you to keep the HTML separate.

Regarding ISP limitations and CGI, this person's question made it sound like the company would have their own servers and would not be subject to this problem. With FastCGI more widely available, that's another option for running Perl fast.

Something that PHP users often don't realize is that many ISPs run PHP through CGI. They do this for security reasons. Next time you are evaluating an ISP for PHP, check to make sure they offer PHP through mod_php or FastCGI, not just through CGI.

UPDATE: Also, make sure your ISP's PHP offering includes a code cache, because without one PHP doesn't come close to Perl's performance.