Formmail on Windows Server

Hi, I have a form handler sript formMail.cgi and it is in my CGI bin. I have a
form that points to the file in the CGI bin.
With the notes that came with the script it says that you may need to change
execute permissions and point chmod to 755. I guess that, as I have not done
this, this is why my form does not work and when submitted http error 404 comes
up.
I have been told by my hosting company that in order to change permissions I
will need to cross to Linux server as permissions cannot be changed under a
Windows server. Is this true?
I need to get this form working for a client but feel uneasy about going to
Linux. You can see the form at www.nailseaphotographics.co.uk (A testing Site).
Can anyone offer any advice. Surely I should be able to create and use a form
on a Windows server.
I thank you in anticipation of your help.
Graham