Well, for my understanding CGI sripts is also part of the PHP scripts, just the different is PHP running on APache mode which is load faster, and CGI run on process, which slower but more secured. If a hosting site support PHP, they should have support PHP-CGI scritpts.
I feel you are wrong, because CGI is related to Perl script. If any host supports Perl script means, it supports CGI as well. These days php is supported by almost all hosts, it does not mean it supports CGI as well if I'm not wrong.