If you are still not able to solve ur problem, then use the mail function as follows.
mail("To Email","Subject","Message","From:Your Name <your Email Address>");
I hope this will solve the problem as it did mine when I was having the same problem with the linux server.