Matthew_182
Usa PHP Mailer:
http://phpmailer.sourceforge.net
Envia tu e-mail por SMTP (si es qu los "sockets" no lo han desactivado tambièn en ese servicio de hosting gratuito) .. y usa alguna cuenta de correo POP/SMTP que dispongas o te busques (nada de "hotmail" ni yahoo .. ni gmail .. ..)
Y sino .. paga por un servicio de hosting y dejate de problemas .. mira precios tienes buenas ofertas.
Un saludo,