Pues tendrás que olvidarte de la función mail() de PHP original para enviar el e-mail en sí .. (por qué si dices que es gratuito .. menos te va a dejar hacer algo tipo: ini_set("SMTP","tu.smtp.tal"); como para cambiar la configuración de PHP en tiempo de ejecución y usar tu própio servidor SMTP que a su vez no requiera autentificación para enviar/usarlo).
Podrías usar la classe:
PHP Mailer
http://phpmailer.sourceforge.net
Te permite enviar e-mail por SMTP (incluso bajo servidores SMTP que requieran autentificación como lo són hoy por hoy la mayoría) entre otras cosas interesantes como la de facilitarte la taréa para enviar datos adjuntos (attach) y otras cosas.
Sólo te faltará conseguirte un servidor SMTP por el cual enviar .. Tal vez el de alguna de tus cuentas que uses de correo (no Hotmail y web-mails .. sólo SMTP/POP ..)
Un saludo,