Hola Diegote:
El problema esta en la direccción, en tu caso todo lo que este en "public_html" al intentar accesarlo por HTTP debes de hacerlo por medio de "http://www.tusitio.com", entonces en esta caso como tu CGI esta en "public_html/cgi-bin/formail.pl" la direccion en tu action que debes de poner es de:
http://www.midominio.com/cgi-bin/formmail.pl
Recuerda tambien que UNIX a diferencia de Windows es sensible a las mayúsculas, así que no es lo mismo formail.pl que FormMail.pl.
SALUDOS