As noted, you should use your own email (or a valid email address on your server) as the From: and Reply-To: headers, otherwise you're allowing the origin of the email to be spoofed which will a) most likely cause many spam filters to flag your message, and b) cause problems with many MTA's (as you're experience right now, actually).
Also not that the line endings to separate headers is a CRLF, that is "\r\n" in PHP code (well, it's that way for MTA's that follow the rules... unless your host is using a poorly-designed MTA, the CRLF line ending should work); more information on this can be found in the manual: [man]function.mail[/man].
EDIT: Also, while we're on the topic of bad practices... in your present code, you're allowing users to insert information directly into the headers of the e-mail without any form of validation or sanitization, meaning they can add whatever headers they want. They could change the from address, subject and message and then send the e-mail out that they have composed to thousands of people (or until your host notices the flood of email traffic and suspends your account).
Long story short... sanitize the input - stripping new lines should be all you need, depending on the header you're allowing them to specify.
