you probably have an earlier version of the contact form files that did not use the template, if you re download the contact from files, you will see the templates folder.
No, The contact form solution pack cannot work with the formmail.pl script.
for the captcha to work, the form must post to itself, since the form must post to itself, it cannot post to the formmail.pl script.
to maintain the values of the form elements on failed validation, add the following code to the value for each form element:
<?php echo(ValidatedField("contact","<element name>")) ?>
substitute <element name> with the correct name for the element.
you should double check with your host that they support sending emails using the PHP mail() function.