A ver como es esto: Para ejecutar un CGI de PERL necesitas tener instalado en el servidor el interprete de PERL, generalmente los servidores ya traen instalado el interprete y algun que otro script como el formmail que tu mensionas, de manera que no tengas que hacer nada.
Si tu servidor no soporta CGI debes cambiarte a uno que si lo tenga, si con telefonica te refieres a la empresa de telefonia, te recomiendo que te cambies de hosting a uno que si tenga CGI como ser
www.******.com
Si no, para un simple formulario tienes empresas que te dejan usar su script CGI gratuitamente como ser
www.melodysoft.com ahi no necesitas instalar nada, ya que usas uno que ya esta instalado.
Bueno, espero que te sirva y ya sabes, cualquier cosa preguntanos.
Saludos
PD: Perdona los acentos, es que lo escribí desde una notebook y no tiene para hacer acentos.